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



             

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


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

Следствие. Пусть

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

Действительно, в качестве

\ {\cal M}
можно взять м.Т., определяемую выражением
\ \mathbf{par}_*(\mathcal{M}_1,\mathbf{par}_*(\mathcal{M}_2, \mathbf{par}_*(\mathcal{M}_3,\ldots \mathbf{par}_*(\mathcal{M}_{m-1},\mathcal{M}_m)\ldots ))).
\\ Будем обозначать эту машину Тьюринга как
\mathbf{par}_*(\mathcal{M}_1,\mathcal{M}_2, \ldots , \mathcal{M}_m)
.




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