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

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

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

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

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

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

Будем считать (используя лемму 1 ), что завершает работу в стандартных конфигурациях. Требуемая м.Т. будет моделировать работу , используя "многоэтажную" ленту . Содержимое ячеек на 1-ом (нижнем) этаже будет на каждом такте совпадать с содержимым тех же ячеек , на 2-ом этаже будет копироваться содержимое левой полуленты: на нем в i-ой ячейке

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

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

1. 1) На первом этапе отмечается 1-я ячейка и содержимое входа переписывается на 1-ый этаж трехэтажной ленты:
   

2. Затем

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

   Кроме того, для a =

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

   Сдвиги

   
   из 1-ой ячейки налево в -1-ю и обратно моделируются переходом с одного этажа на другой в 1-ой ячейке
   
   

3. После завершения моделирования

   
   результат записан в начальных ячейках на 1-ом этаже.
   
   переводит его в первоначальный алфавит ?.
   

   Проверка правильности работы м.Т.

   
   предоставляется читателю (см. задачу 9.4).

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

---

---

Главная сайта

---