Граф переходов

Этот граф является ориентированным и строится следующим образом: вершины графа соответствуют состояниям МТ, дуга ведет из одного состояния в другое и подписывается, согласно правилу перехода из одного состояния в другое без указания самого состояния (рис.3).

Рис.3

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

Внешний алфавит. Конечное множество, элементы которого называются буквами (символами). Одна из букв этого алфавита должна представлять собой пустой символ.

Внутренний алфавит. Конечное множество состояний управляющего устройства. Одно из состояний (например, q1) должно быть начальным (запускающим программу). Еще одно из состояний (q0) должно быть конечным (завершающим программу) – состояние останова.

Систему команд тем или иным способом.

(с22-с23)

Далее условимся отдельные символы алфавита обозначать латинскими буквами, а слова греческими.

Машина обозревает первый символ слова и слева написано слово МТ находится в состоянии q_i.

Детерминизм МТ заключается в том, что всякая конфигурация однозначно определяет следующую конфигурацию.

Эта последовательность называется протоколом.

Если в протоколе какая-либо конфигурация повториться, то машина зациклится.

K₀→K₁→…→ K_i →K_i+1 →…→K_i →K_i+1→…

Иными словами, если МТ выдает результат, т.е. останавливается, то ни одна конфигурация в её протоколе не повторяется.

Стандартная начальная конфигурация имеет вид (т.е. МТ всегда, в начале, обозревает крайний левый символ), а стандартная заключительная (это означает, что в момент остановки на ленте нет мусора, все промежуточные результаты стерты).

Когда вид начальной конфигурации совпадает с видом заключительной конфигурации легко предавать управление от одной МТ к другой, т.е. начинать новые вычисления.

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

добавим к МТ два новых состояния q^` q`` и команды

МТ^` эквивалентна МТ в следующем смысле:

Лемма 1. Для всякой МТ Т можно построить эквивалентную МТ Т^/, у которой все заключительные конфигурации стандартны.