Пусть поставлена вычислительная задача, которую сумели разбить на части. Более того, для решения каждой из частей задачи предоставлены соответствующие машины Тьюринга. Как организовать совместную работу этих машин для решения полной задачи? Ответ на вопрос заключается во введении некоторых операций над машинами Тьюринга, которые называются композициями машин.
Первая композиция — последовательное соединение машин.
Пусть даны две программы машины Тьюринга. Первая получает на ленте исходные данные и начинает работу. После конечного числа шагов попытка выбрать из таблицы (программы) очередную команду заканчивается безрезультатно — соответствующая клетка таблицы пуста. Первая программа должна остановиться, на ленте остается некоторое число — значение вычисленной функции. Но в этот момент начинает работать вторая программа, заданная другой таблицей и использующая результат
работы первой программы в качестве исходных данных. Через
конечное число шагов вторая программа завершает свою работу,
оставив на ленте результат последовательного выполнения двух
программ. .
Для организации такой работы достаточно построить объединенную таблицу машины Тьюринга, приписав к первой таблице вторую (справа) и заполнив пустые клетки первой таблицы командой i p1 S — командой перехода к первому (начальному) состоянию p1, второй программы; здесь i — буква алфавита, соответствующая строке, в которой находится пустая клетка.
Второй вид композиции — итерация (повторение) машины Тьюринга.
В этом случае повторяем выполнение одной и той же программы конечное число раз. По окончании первого выполнения на ленте остается промежуточный результат, который является исходными данными для второго выполнения и т. д Для обеспечения второго и последующих выполнений необходимо в некоторые пустые клетки таблицы вписать команду перехода на начало: i qi S. Во все пустые клетки эту команду вписать нельзя, так как измененная таким образом программа не сможет заканчиваться.
Итерация машины Тьюринга соответствует конструкциям циклов в языках программирования.