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


             

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


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

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

Действительно, в качестве
можно взять м.Т., определяемую выражением
\\ Будем обозначать эту машину Тьюринга как
.


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