§ 2. Машины Тьюринга

Решаемые на графах задачи могут быть двух типов: оптимизационные, т. е. такие в которых из допустимого множества решений необходимо выбрать такое, вес которого минимален (максимален), и распознавательные, решение которых заключается в получении ответа «да» или «нет» (истина или ложь). При этом каждой оптимизационной задаче можно сопоставить ее распознавательный вариант так, что если имеется полиномиальный алгоритм решения первой, то найдется и полиномиальный алгоритм решения второй, и наоборот. Поэтому в дальнейшем будем рассматривать только распознавательные задачи. Одним из алгоритмов, решающих такие задачи, является машина Тьюринга, предложенная в 1936 г. А. М. Тьюрингом в качестве модели «любого возможного вычисления».

Машина Тьюринга (МТ) состоит из ленты, разделенной на ячейки, в каждой из которых может храниться символ из конечного множества состояний, и конечного управления, которое может находиться в одном из состояний [15].

Конечное управление

…

В

В

В

В

…

Рис. 2.1. Машина Тьюринга.

Изначально на ленте записана цепочка символов конечной длины – вход, слева и справа от которой записаны специальные символы (В), называемые пустыми символами, или пробелами. Ленточная головка устанавливается на какую-либо ячейку, называемую обозреваемой. В начальный момент обозревается крайняя левая ячейка входа.

Управление состоит из переходов, в каждом из которых выполняются следующие действия:

– машина читает символ из ячейки, против которой стоит головка;

– записывает в эту ячейку символ (может и тот же самый);

– меняет свое состояние (следующее состояние может совпадать с предыдущим);

– сдвигает головку влево или вправо.

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

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

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

Определение 2.5. Будем говорить, что НМТ решает распознавательную задачу за полиномиальное время, если найдется такой полином p(n), что каждый вход длиной n этой задачи имеет ответ «да» тогда и только тогда, когда существует такой выбор троек значений, который останавливает работу машины, сообщив этот ответ, и время ее работы не превосходит p(n).

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