Последовательная и параллельная композиции машин Тьюринга - часть 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)$

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