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

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

Лемма 9.3.(Последовательная композиция) Пусть м.Т.

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

Доказательство Действительно, пусть

а

Используя лемму 9.1, будем считать, что у

заключительные конфигурации стандартны. Тогда легко проверить, что функция h вычисляется следующей м.Т. где P= P1 P2 {qf2 a q01 aН | a ?2} .

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

Лемма 9.4. (Параллельная композиция) Пусть м.Т.

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

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

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

1. Начав в конфигурации (p0x*y), находит 1-ый символ y
2. и переходит в конфигурацию (x*q02y).
3. Работая как
   
   вычисляет g(y) и переходит при этом в конфигурацию (x*qf2g(y)).
4. Переписывает *x после g(y) и переходит в конфигурацию g(y)*q01x).
5. Работая как
   
   вычисляет f(x) и переходит при этом в конфигурацию (g(y)*qf1f(x).
6. Меняет
   
   и
   
   местами и останавливается.

Корректность этапов 2 и 4 следует из односторонности

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

Построенную в этой лемме м.Т.

, полученную в результате параллельной композиции и , будем обозначать как . Здесь индекс * указывает символ, которым отделяются аргументы и

на ленте

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

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

Следствие. Пусть - машины Тьюринга, вычисляющие функции f1, … , fm, соответственно. Пусть символ * не входит в алфавиты этих машин. Тогда существует м.Т. , перерабатывающая любой вход вида x1*x2* … *xm (xi ?i*, i=1,…, m) в выход f1(x1)*f2(x2)* … *fm(xm).

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


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

---