Последовательная композиция МТ. (с30-с31)

Пусть даны две машины Тьюринга Т₁ и Т_2, которые вычисляют соответствующие функции в одном и том же алфавите. Тогда существует машина Тьюринга Т, которая вычисляет функцию . При этом для любого слова функция определена в том и только в том случае, когда определена и определена.

Параллельная композиция. Пусть м.Т. вычисляет функцию f(x), а м.Т. - функцию g(x) и символ * не входит в алфавит м.Т. . Тогда существует м.Т. которая по любому входу вида x*y выдает результат f(x)*g(y), т.е. вычисляет функцию H(x*y) = f(x)*g(y).