Последовательная и параллельная композиции машин Тьюринга
Используя возможность моделирования произвольной м.Т. на м.Т. со стандартными заключительными конфигурациями, легко установить справедливость следующей леммы о последовательной композиции машин Тьюринга.
заключительные конфигурации стандартны. Тогда легко проверить, что функция 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). Определим теперь м.Т.
которая работает следующим образом.
Начав в конфигурации (p0x*y), находит 1-ый символ y
и переходит в конфигурацию (x*q02y).
Работая как
вычисляет g(y) и переходит при этом в конфигурацию (x*qf2g(y)).
Переписывает *x после g(y) и переходит в конфигурацию g(y)*q01x).
Работая как
вычисляет f(x) и переходит при этом в конфигурацию (g(y)*qf1f(x).
Меняет
и
местами и останавливается.
Корректность этапов 2 и 4 следует из односторонности
и
а реализация этапов 1, 3 и 5 достаточно очевидна (см. задачу 9.6).
Построенную в этой лемме м.Т.
, полученную в результате параллельной композиции
и
, будем обозначать как
. Здесь индекс * указывает символ, которым отделяются аргументы
и
на ленте
. Этот символ может быть любым символом, не входящим в алфавит машины
. Например,
будет обозначать параллельную композицию машин
и
, в которой их аргументы отделены символом #.
Конструкцию параллельной композиции можно обобщить на произвольное конечное число машин Тьюринга.
Следствие. Пусть
- машины Тьюринга, вычисляющие функции f1, … , fm, соответственно. Пусть символ * не входит в алфавиты этих машин. Тогда существует м.Т.
, перерабатывающая любой вход вида x1*x2* … *xm (xi
местами и останавливается.
