Недетерминированная машина Тьюринга

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

Устройство

Детерминированная (обычная, классическая) машина Тьюринга имеет функцию перехода, которая по комбинации текущего состояния и символа на ленте определяет три элемента: символ, который будет записан на ленте, направление смещения головки по ленте и новое состояние конечного автомата. Например, X на ленте в состоянии 3 однозначно определяет переход в состояние 4, запись на ленту символа Y и перемещение головки на одну позицию влево.

В случае недетерминированной машины Тьюринга, комбинация текущего состояния автомата и символа на ленте может допускать одновременно параллельно несколько переходов в следующие состояния. Например, X на ленте и состоянии 3 допускает как состояние 4 с записью на ленту символа Y и смещением головки вправо, так и состояние 5 с записью на ленту символа Z и смещением головки влево. Таким образом недерминированная машина Тьюринга может одновременно находится во многих состояниях одновременно.

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

Определение

Формально, недетерминированная машина Тьюринга задаётся в виде упорядоченной шестёрки элементов некоторых множеств: [math]\displaystyle{ M=(Q, \Sigma, \iota, \sqcup, A, \delta) }[/math], где:

[math]\displaystyle{ Q }[/math] — конечное множество состояний
[math]\displaystyle{ \Sigma }[/math] — конечное множество символов (алфавит ленты)
[math]\displaystyle{ \iota \in Q }[/math] — начальное состояние
[math]\displaystyle{ \sqcup }[/math] — символ пробела ([math]\displaystyle{ \sqcup \in \Sigma }[/math])
[math]\displaystyle{ A \subseteq Q }[/math] — конечное множество допускающих состояний
[math]\displaystyle{ \delta: Q \backslash A \times \Sigma \rightarrow \left( Q \times \Sigma \times \{L,R\} \right) }[/math] — многозначное отображение из пары состояние-символ, называемое функцией перехода.

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

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

Моделирование недетерминизма требует значительно больше времени, вопрос об оценке разницы затрат открыт: в частном случае ограничения по времени в виде полинома от длины входа этот вопрос представляет собой классическую задачу «P = NP».

Класс алгоритмов, выполняемых за полиномиальное время на недетерминированных машинах Тьюринга, называется классом NP.

Пример

Рассмотрим задачу проверки того, что данное b-разрядное целое число N (2^b-1≤N<2^b) является составным. Тогда b — длина входных данных, по отношению к которой рассматривается время вычисления. Ответ «ДА» — число составное и «НЕТ» — простое. Эта задача является комплементарной к тесту на простоту.

Недетерминированный алгоритм для этой задачи может быть, например, следующий:

Выбрать недетерминированно целое число m такое что 1<m<N.
Разделить нацело N на m, остаток обозначим через a.
Если a=0 выдать ответ «ДА» (m тогда — делитель N), иначе выдать ответ «НЕТ».

(Алгоритм написан не непосредственно в виде определения машины Тьюринга.)

Во времени вычисления этого алгоритма определяющей частью является время выполнения деления, которое может быть выполнено за O(b²) шагов, что представляет собой полиномиальное время. Таким образом, задача находится в классе NP.

Для реализации такого времени вычисления требуется удачно выбирать число m или выполнять вычисления по всем возможным путям (для всех возможных m) одновременно на множестве копий машины.

Если моделировать этот алгоритм на детерминированной машине Тьюринга, пробуя по очереди все возможные варианты, требуется проверить N-2=O(2^b) ветвей. Таким образом, общее время вычислений будет O(b²2^b) шагов, что представляет собой уже экспоненциальное время, которое существенно больше, чем полиномиальное время. Таким образом, этот алгоритм не попадает в класс P. (Однако, могут быть применены другие, более быстрые алгоритмы для этой задачи, которые работают за полиномиальное время и, таким образом, задача попадает в класс P.)

Литература

Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман. Введение в теорию автоматов, языков и вычислений = Introduction to Automata Theory, Languages, and Computation. — М.: «Вильямс», 2002. — 528 с. — ISBN 0-201-44124-1.
Карпов Ю. Г. Теория автоматов. — Питер, 2003. — ISBN 5-318-00537-3.