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

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

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

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

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

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

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

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

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

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

Последовательная и параллельная композиции машин Тьюринга

Используя возможность моделирования произвольной м.Т. на м.Т. со стандартными заключительными конфигурациями, легко установить справедливость следующей леммы о последовательной композиции машин Тьюринга.

Лемма 9.3.( Последовательная композиция ) Пусть м.Т.   вычисляет функцию f(x), а м.Т.   - функцию g(x). Тогда существует м.Т.   вычисляющая функцию h(x) = f(g(x)).

Доказательство Действительно, пусть   а  . Используя лемму 9.1, будем считать, что у   заключительныеконфигурации стандартны. Тогда легко проверить, что функция h вычисляется следующей м.Т.   где  .

Покажем, что работу двух м.Т. можно комбинировать так, чтобы в заключительной конфигурациисодержались результаты работы каждой из них над независимыми входами.

Лемма 9.4. ( Параллельная композиция ) Пусть м.Т.   вычисляет функцию f(x), а м.Т.   - функцию g(x) и символ * не входит в алфавит м.Т.  . Тогда существует м.Т.   которая по любому входу вида x*y выдает результат f(x)*g(y), т.е. вычисляет функцию H(x*y) = f(x)*g(y).

Доказательство. Пусть   и   - м.Т. Не ограничивая общности, будем считать, что эти машины односторонние (по Лемме 2). Определим теперьм.Т.  , которая работает следующим образом.

1. Начав в конфигурации (p₀x*y), находит 1-ый символ y

2. и переходит в конфигурацию (x*q₀²y).

3. Работая как   вычисляет g(y) и переходит при этом в конфигурацию (x*q_f²g(y)).

4. Переписывает *x после g(y) и переходит в конфигурацию g(y)*q₀¹x).

5. Работая как   вычисляет f(x) и переходит при этом в конфигурацию (g(y)*q_f¹f(x).

6. Меняет   и   местами и останавливается.

Корректность этапов 2 и 4 следует из односторонности   и   а реализация этапов 1, 3 и 5 достаточно очевидна (см. задачу 9.6).

Построенную в этой лемме м.Т.  , полученную в результате параллельной композиции   и  , будем обозначать как  . Здесь индекс * указывает символ, которым отделяются аргументы   и   на ленте  . Этот символ может быть любым символом, не входящим в алфавит машины  . Например,   будет обозначать параллельную композициюмашин   и  , в которой их аргументы отделены символом #.

Конструкцию параллельной композиции можно обобщить на произвольное конечное число машин Тьюринга.

Следствие. Пусть   - машины Тьюринга, вычисляющие функции f₁, ... , f_m, соответственно. Пусть символ * не входит в алфавиты этих машин. Тогда существует м.Т.  , перерабатывающая любой вход вида x₁*x₂* ... *x_m   в выход f₁(x₁)*f₂(x₂)* ... *f_m(x_m).

Действительно, в качестве   можно взять м.Т., определяемую выражением  .\\ Будем обозначать эту машину Тьюринга как  .