Композиции машин Тьюринга. Тезис Тьюринга

1°. Машина последовательной обработки. Пусть и – машины Тьюринга в одном алфавите. Построим третью машину Тьюринга, работа которой будет равносильна последовательной работе машин и .

Пусть машина имеет множество состояний , а – . Назначим заключительное состояние машины начальным состоянием машины . Определим машину более точно. Пусть она имеет множество состояний , а ее команды получаются из команд машин и следующим образом:

– в командах машины всюду заменим на ;

– в командах машины всюду заменим на .

Такую композицию машин и называют машиной последовательной обработки и обозначают , а также изображают блок-схемой СЛЕДОВАНИЕ (рис. 1).

Рис. 1. Структура СЛЕДОВАНИЕ

Пример 4. Композиция машин “+1” и дает машину, которая после прибавления 1 возвращает головку на правый символ результата. Программа новой машины:

2°. Машина условного перехода. Пусть , и – машины Тьюринга в одном алфавите. Машина имеет множество внутренних состояний , среди которых два заключительных. Машина – , машина – .

Построим машину, которая работает следующим образом: сначала записанное на ленту слово обрабатывает машина , которая в зависимости от процесса обработки может остановиться либо в состоянии , либо в состоянии . В первом случае образовавшееся на ленте слово обрабатывается машиной , во втором – .

Для построения такой машины надо выполнить действия:

1) переобозначить состояния машин и :

, …, ;

, …, ;

2) заменить в программе машины на , на и добавить к измененному таким образом тексту программы машины программы машин и с переобозначенными состояниями.

Построенная композиция машин , и называется машиной условного перехода и обозначатся блок-схемой РАЗВЕТВЛЕНИЕ (рис. 2).

Если в качестве одной из машин или взять машину , то получим структуру ЦИКЛ (рис. 3).

Рис. 2. Структура РАЗВЕТВЛЕНИЕ Рис. 3. Структура ЦИКЛ