Разветвление или условный переход в композиции машин Тьюринга

Если заданы машины Тьюринга и , вычисляющие словарные функции и , и машина , вычисляющая некоторый предикат P(a) с восстановлением (т.е. без стирания слова a), то для реализации разветвления может быть построена машина Тьюринга , вычисляющая функцию:

Разветвление машин Тьюринга на схемах композиции изображается следующим образом:

и обозначается , здесь – результат работы машины , принимающий значения «1», если предикат P(a)= ” true” и «0», если предикат P(a)= “ false”, – машина Тьюринга, реализуюшая копирование входного слова .

 

4. Цикл в композиции машин Тьюринга

Цикл в композиции МТ реализуется по тем же принципам, что и разветвление.

Циклическим будем считать следующий алгоритм :

«пока P(a)= ” true”, выполнять »,

где a – слово на ленте перед первым выполнением и после очередного выполнения.

Для изображения цикла введем некоторые обозначения, пусть:

– машина Тьюринга, реализующая вычисление предиката P(a);

– МТ, реализующая копирование входного слова ;

– МТ, выполняемая в цикле и реализующая ;

– МТ, выполняемая при выходе из цикла и реализующая .

Тогда, циклическая композиция машин Тьюринга или цикл, может быть изображена следующим образом:

 

Программирование с помощью композиций машин Тьюринга:

1) построение блок-схем сложных алгоритмов такой степени детализации, что их блоки соответствуют элементарным МТ;

2) построение элементарных МТ, реализующих простые блоки;

3) объединение элементарных МТ в композицию МТ.

Пример. Записать композицию МТ для реализации функции z=y*x.

– машина Тьюринга, реализующая копирование входного слова;

– МТ, реализующая функцию установки константы ноль;

– МТ, вычисляющая предикат с восстановлением ;

– МТ, реализующая функцию выбора -того аргумента из аргументов;

– МТ, реализующая функцию уменьшение аргумента на 1 в унарном коде (вытирает крайний левый символ );

– МТ, выполняющая сложение двух чисел в унарном коде.

Следует отметить, что в любом случае необходимо в начале выполнения алгоритма выполнить проверку входных данных на корректность (например, равенство 0 аргумента при делении).