КОМПОЗИЦИЯ МАШИН ТЬЮРИНГА

 

Цель работы: получить практические навыки в записи алгоритмов с использованием композиции машин Тьюринга.

 

Теоретическая справка

Вышеперечисленные способы описания МТ практически можно использовать только для несложных алгоритмов, в противном случае описание становится слишком громоздким. Машины Тьюринга для сложных алгоритмов могут строиться с использованием уже имеющихся элементарных МТ и такое построение называется композицией МТ.

Опишем 4 основных способа композиции МТ:

- последовательная композиция ( суперпозиция );

- параллельная композиция;

- разветвление

- цикл