Конструкцию параллельной композиции можно обобщить
Конструкцию параллельной композиции можно обобщить на произвольное конечное число машин Тьюринга.
Следствие. Пусть
- машины Тьюринга, вычисляющие функции f1, … , fm, соответственно. Пусть символ * не входит в алфавиты этих машин. Тогда существует м.Т.
, перерабатывающая любой вход вида x1*x2* … *xm (xi
?i*, i=1,…, m) в выход f1(x1)*f2(x2)* … *fm(xm).
Действительно, в качестве
можно взять м.Т., определяемую выражением
\\ Будем обозначать эту машину Тьюринга как
.
Содержание Назад Вперед