Полубесконечная ленточная машина Тьюринга
Машина Тьюринга с полубесконечной лентой имеет левый конец, но не правый. Левый конец ограничен маркером конца.
Это двухдорожечная лента -
Upper track - Представляет клетки справа от исходного положения головы.
Lower track - Он представляет ячейки слева от исходного положения головы в обратном порядке.
Входная строка бесконечной длины изначально записывается на ленте в непрерывных ячейках ленты.
Машина запускается из исходного состояния q0и голова сканирует от левого крайнего маркера «Конец». На каждом шаге он считывает символ на ленте под его головой. Он записывает новый символ в эту ячейку ленты, а затем перемещает головку на одну ячейку ленты влево или вправо. Функция перехода определяет действия, которые необходимо предпринять.
Он имеет два особых состояния, называемых accept state а также reject state. Если в какой-то момент он переходит в принятое состояние, ввод принимается, а если он переходит в состояние отклонения, ввод отклоняется TM. В некоторых случаях он продолжает работать бесконечно, не будучи принят или отклонен для некоторых определенных входных символов.
Note - Машины Тьюринга с полубесконечной лентой эквивалентны стандартным машинам Тьюринга.