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

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

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