Если заданы машины Тьюринга 
и 
, вычисляющие словарные функции 
и 
, и машина 
, вычисляющая некоторый предикат P(a) с восстановлением (т.е. без стирания слова a), то для реализации разветвления может быть построена машина Тьюринга 
, вычисляющая функцию:
Разветвление машин Тьюринга на схемах композиции изображается следующим образом:
и обозначается 
, здесь 
– результат работы машины , принимающий значения «1», если предикат P(a)= ” true” и «0», если предикат P(a)= “ false”, 
– машина Тьюринга, реализуюшая копирование входного слова 
.
4. Цикл в композиции машин Тьюринга
Цикл в композиции МТ реализуется по тем же принципам, что и разветвление.
Циклическим будем считать следующий алгоритм :
«пока P(a)= ” true”, выполнять 
»,
где a – слово на ленте перед первым выполнением и после очередного выполнения.
Для изображения цикла введем некоторые обозначения, пусть:
– машина Тьюринга, реализующая вычисление предиката P(a);
– МТ, реализующая копирование входного слова ;
– МТ, выполняемая в цикле и реализующая 
;
– МТ, выполняемая при выходе из цикла и реализующая .
Тогда, циклическая композиция машин Тьюринга или цикл, может быть изображена следующим образом:
Программирование с помощью композиций машин Тьюринга:
1) построение блок-схем сложных алгоритмов такой степени детализации, что их блоки соответствуют элементарным МТ;
2) построение элементарных МТ, реализующих простые блоки;
3) объединение элементарных МТ в композицию МТ.
Пример. Построить композицию МТ, реализующую 
.
– машина Тьюринга, реализующая копирование входного слова;
– МТ, реализующая функцию установки константы ноль;
– МТ, вычисляющая предикат с восстановлением 
;
– МТ, реализующая функцию выбора 
-того аргумента из 
аргументов;
– МТ, реализующая функцию уменьшение аргумента 
на 1 в унарном коде (вытирает крайний левый символ 
);
– МТ, выполняющая сложение двух чисел в унарном коде.
Следует отметить, что в любом случае необходимо в начале выполнения алгоритма выполнить проверку входных данных на корректность (например, равенство 0 аргумента при делении).
Задание на лабораторную работу
Построить машину Тьюринга, вычисляющую функцию 
из задания к лабораторной работе №1 “Рекурсивные функции”.
Машину Тьюринга представить, как композицию элементарных МТ, выполняющих операции: копирование аргумента, сложение, умножение, арифметическое вычитание, нахождение целой части и остатка от деления, сравнения чисел, выделение аргумента. Недостающие элементарные МТ описать любым известным способом.
Контрольные вопросы
1. Композиции машин Тьюринга и область их применения?
2. Дать определение и привести обозначение суперпозиции или последовательной композиции машин Тьюринга.
3. Дать определение и привести обозначение паралелльной композиции машин Тьюринга.
4. Двухэтажная и 
этажная ленты, использование их в паралельной композиции машин Тьюринга.
5. Дать определение и привести обозначение разветвления или условного перехода в композиции машин Тьюринга.
6. Дать определение и привести обозначение цикла в композиции машин Тьюринга.
Лабораторная работа № 4
