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

         

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


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

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

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


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