Односторонние машины Тьюринга

Машина Тьюринга

$Односторонние машины Тьюринга$

называется односторонней, если в процессе вычисления ее головка никогда не сдвигается левее начальной ячейки (т.е. всегда находится в ячейках с положительными номерами).

Лемма 9.2. Для всякой м.Т.

$Односторонние машины Тьюринга$

можно построить эквивалентную одностороннюю м.Т.

$Односторонние машины Тьюринга$

Доказательство. Пусть

$Односторонние машины Тьюринга$

Будем считать (используя лемму 1 ), что

$Односторонние машины Тьюринга$

завершает работу в стандартных конфигурациях. Требуемая м.Т.

$Односторонние машины Тьюринга$

будет моделировать работу

$Односторонние машины Тьюринга$

, используя "многоэтажную" ленту . Содержимое ячеек на 1-ом (нижнем) этаже будет на каждом такте совпадать с содержимым тех же ячеек

$Односторонние машины Тьюринга$

, на 2-ом этаже будет копироваться содержимое левой полуленты: на нем в i-ой ячейке

$Односторонние машины Тьюринга$

будет тот же символ, что и в -i-ой ячейке

$Односторонние машины Тьюринга$

. Кроме того, на 3-ем этаже в 1-ой ячейке будет стоять отмечающий ее символ #. Таким образом, ?' = ? ? ? ? {

, # }

?. Работа

$Односторонние машины Тьюринга$

будет происходить следующим образом.

1) На первом этапе отмечается 1-я ячейка и содержимое входа переписывается на 1-ый этаж трехэтажной ленты:
$Односторонние машины Тьюринга$
Затем
$Односторонние машины Тьюринга$
моделирует работу
$Односторонние машины Тьюринга$
, используя для работы на 2-ом этаже дубликаты состояний (со штрихами) и команды со сдвигами в обратном направлении. Для команды q ,a
r , b ,C из P и для всех c
? в P' поместим команды:

$Односторонние машины Тьюринга$

Кроме того, для a =
сохраним и старые команды для работы на впервые посещаемых ячейках:

$Односторонние машины Тьюринга$

Сдвиги
$Односторонние машины Тьюринга$
из 1-ой ячейки налево в -1-ю и обратно моделируются переходом с одного этажа на другой в 1-ой ячейке
$Односторонние машины Тьюринга$
$Односторонние машины Тьюринга$
После завершения моделирования
$Односторонние машины Тьюринга$
результат записан в начальных ячейках на 1-ом этаже.
$Односторонние машины Тьюринга$
переводит его в первоначальный алфавит ?.

$Односторонние машины Тьюринга$

Проверка правильности работы м.Т.
$Односторонние машины Тьюринга$
предоставляется читателю (см. задачу 9.4).

Содержание раздела