Односторонние машины Тьюринга
Машина Тьюринга
называется односторонней, если в процессе вычисления ее головка никогда не сдвигается левее начальной ячейки (т.е. всегда находится в ячейках с положительными номерами).Лемма 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).