Пусть заданы машины Тьюринга T1 и T2, имеющие общий внешний алфавит А = {a0, a1, ..., am} и внутренние состояния Q1 = {q0, q1,… qn} и Q2 = {q0, q1,
..., qt} соответственно. Композицией или произведением машины T1
и машины T2
будем называть машину Т с тем же внешним алфавитом А = {a0, а1, ...,
am} и набором внутренних состояний Q = {q0, q1,..., q2,, qn+1,..., qn+1} и программой, эквивалентной последовательному выполнению программ машин Т1
и Т2:
Т = T1 * T2..
Таким же образом определяется операция возведения в степень: n-й степенью машины Т называется произведение T...Т
c n сомножителями.
Операция итерации применима к одной машине и определяется следующим образом. Пусть машина T1
имеет несколько заключительных состояний. Выберем ее r-е заключительное состояние и отождествим его в схеме машины с ее начальным состоянием. Полученная машина T является результатом итерации машины Т1 : Т = T1.
Прежде чем остановиться на проблеме алгоритмической разрешимости задач обратимся к другим способам формализации понятия алгоритма.