Конструкцию параллельной композиции можно обобщить

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

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

- машины Тьюринга, вычисляющие функции f1, … , fm, соответственно. Пусть символ * не входит в алфавиты этих машин. Тогда существует м.Т.

, перерабатывающая любой вход вида x1*x2* … *xm (xi

?i*, i=1,…, m) в выход f1(x1)*f2(x2)* … *fm(xm).

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

можно взять м.Т., определяемую выражением

\\ Будем обозначать эту машину Тьюринга как