Введение в схемы, автоматы и алгоритмы

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


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

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

Лемма 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).



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