Машина Тьюринга с полубесконечной лентой имеет левый конец, но не имеет правого конца. Левый конец ограничен маркером конца.
Это двухполосная лента —
-
Верхняя дорожка — представляет ячейки справа от начальной позиции головы.
-
Нижняя дорожка — представляет ячейки слева от начальной позиции головы в обратном порядке.
Верхняя дорожка — представляет ячейки справа от начальной позиции головы.
Нижняя дорожка — представляет ячейки слева от начальной позиции головы в обратном порядке.
Входная строка бесконечной длины изначально записывается на ленту в непрерывных ячейках ленты.
Машина запускается из начального состояния q 0, а головка сканирует левый крайний маркер «Конец». На каждом шаге он читает символ на ленте под своей головой. Он записывает новый символ в эту ячейку ленты, а затем перемещает головку в левую или правую ячейку ленты. Функция перехода определяет действия, которые необходимо предпринять.
У него есть два специальных состояния: состояние принятия и состояние отказа . Если в любой момент времени он входит в принятое состояние, ввод принимается, и если он входит в состояние отклонения, ввод отклоняется TM. В некоторых случаях он продолжает работать бесконечно, не будучи принятым или отклоненным для некоторых определенных входных символов.
Примечание. Машины Тьюринга с полубесконечной лентой эквивалентны стандартным машинам Тьюринга.