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



             

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


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

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

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

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

\ {\cal M}_1 = <Q_1, {\Sigma}_1, P_1,q_0^1, q_f^1>,\
а
\ {\cal M}_2 = <Q_2, {\Sigma}_2, P_2,q_0^2, q_f^2>.

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

\ {\cal M}_2
заключительные конфигурации стандартны. Тогда легко проверить, что функция h вычисляется следующей м.Т.
\ {\cal M} = <Q_1 \cup Q_2, {\Sigma}_1 \cup {\Sigma}_2, P, q_0^2, q_f^1>,\
где P= P1
P2
{qf2 a
q01 aН | a
?2} .

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

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

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

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

\ {\cal M}_1 = <Q_1, {\Sigma}_1, P_1,q_0^1, q_f^1>
и
\ {\cal M}_2 = <Q_2, {\Sigma}_2, P_2,q_0^2, q_f^2>
- м.Т. Не ограничивая общности, будем считать, что эти машины односторонние (по Лемме 2). Определим теперь м.Т.
\ {\cal M} = <Q_1 \cup Q_2 \cup Q^\prime, {\Sigma}_1 \cup {\Sigma}_2 \cup \{*\},P_1 \cup P_2 \cup P^\prime, p_0, p_f>,
которая работает следующим образом.

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

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

\ {\cal M}_2
и
{\cal M}_1,\
а реализация этапов 1, 3 и 5 достаточно очевидна (см. задачу 9.6).

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

\ {\cal M}
, полученную в результате параллельной композиции
\ {\cal M}_1
и
\ {\cal M}_2
, будем обозначать как
\mathbf{par}_*(\mathcal{M}_1,\mathcal{M}_2)
. Здесь индекс * указывает символ, которым отделяются аргументы
\ {\cal M}_1
и
\ {\cal M}_2

на ленте

\ {\cal M}
. Этот символ может быть любым символом, не входящим в алфавит машины
\ {\cal M}_1
. Например,
\mathbf{par}_\#(\mathcal{M}_1,\mathcal{M}_2)
будет обозначать параллельную композицию машин
\ {\cal M}_1
и
\ {\cal M}_2
, в которой их аргументы отделены символом #.




Содержание  Назад  Вперед