Свойства машины Тьюринга

Рассмотрим несколько свойств машин Тьюринга.

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

Доказательство легко следует из правила эквивалентного преобразования исходной машины Тьюринга.

Рис. 4.2.

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

Теорема 2. Для любой машины Тьюринга существует эквивалентная машина Тьюринга, работающая на полу бесконечной ленте.

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

Рис. 4.3.

Затем перенумеруем ячейки, причем будем считать, что символ «*» не содержится в словаре МТ:

Рис. 4.4.

Наконец, изменим машину Тьюринга, удвоив число се состояний, и изменим сдвиг головки считывания-записи так, чтобы в одной группе состояний работа машины была бы эквивалентна ее работе в заштрихованной зоне, а в другой группе состояний машина работала бы так, как исходная машина работает в не заштрихованной зоне. Если при работе МТ встретится символ «*», значит головка считывания-записи достигла границы зоны.

Рис. 4.5.

Начальное состояние новой машины Тьюринга устанавливается в одной или другой зоне в зависимости оттого, в какой части исходной ленты располагалась головка считывания-записи в исходной конфигурации. Очевидно, что слева от ограничивающих маркеров «*» лента в эквивалентной машине Тьюринга не используется.