Теория алгоритмов, формальных языков, грамматик и автоматов. Бильгаева Н.Ц. - 19 стр.

      15) q31 → q31L ε001*11ε        31) q00 → q01L   ε011*111ε
      16) q3* → q3*L ε001*11ε        32) q0ε → qz1R   ε111*111ε

      Из примера видно, что машина Тьюринга из стандартной начальной конфигурации,
имея на ленте аргумент 111 и выполнив совокупность команд 1-32, перешла в стандартное
заключительное состояние, имея на ленте результат ε111*111ε.

      3.8. Машина Тьюринга с полулентой
    В рассмотренных выше определениях машины Тьюринга использовалась бесконечная в
обе стороны лента. Ограничим ленту с одной стороны и покажем, что машина Тьюринга с
правой или левой полулентой эквивалентна машине Тьюринга с бесконечной лентой.
    Говорят, что функция, правильно вычислимая на машине Тьюринга с обычной лентой,
правильно вычислима и на машине Тьюринга с правой полулентой, т.е. для любой машины
Тьюринга Т существует эквивалентная ей машина с правой полулентой TR.
    Идея доказательства этого утверждения основана на следующих предпосылках:
    а) рабочая область ленты ограничена двумя маркерами: неподвижным - слева и
подвижным - справа;
    б) на внутренней части ограниченной области машина Тьюринга с полулентой должна
работать как обычная машина Тьюринга, а при выходе на маркеры она должна освобождать
рабочее пространство, для этого правый маркер может сдвигаться вправо, а при выходе на
левый маркер необходимо сдвинуть всю цепочку вправо;
    в) полученный результат, находящийся между маркерами, в конце работы машины
Тьюринга нужно сдвинуть вплотную к левому маркеру.
    Машина Тьюринга может вычислять функцию с восстановлением, то есть с сохранением
исходных данных. Это позволяет получить на ленте сначала результат, а затем - исходные
данные или наоборот.
    Рассмотрим пример построения машины Тьюринга с правой полулентой, вычисляющей
функцию f(x) = 2x. Алгоритм вычисления данной функции состоит в приписывании нуля к
входной цепочке справа.
    Таблица соответствия данной машины Тьюринга будет иметь следующий вид:


                              <        0       1        >       ε
                       q0            q0 0R   q0 1R    q1 0R
                       q1                                     q2 >L
                       q2   qz < R   q2 0L   q2 1L


    Здесь символ “<“ обозначает левый маркер, а символ “>“ - правый маркер. Машина
Тьюринга, начав работу из стандартной начальной конфигурации, после выполнения
совокупности команд переходит в стандартную заключительную конфигурацию.
Полученный результат располагается между маркерами и сдвинут вплотную к левому
маркеру.

      3.9. Универсальная машина Тьюринга
    До сих пор мы имели дело со специализированными машинами Тьюринга,
предназначенными для решения конкретных задач и отличающимися набором команд,
внутренним и внешним алфавитами. Однако можно построить универсальную машину