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

Устройство

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

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

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

Определение

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

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

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

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

Моделирование недетерминизма требует значительно больше времени, вопрос об оценке разницы затрат открыт: в частном случае ограничения по времени в виде полинома от длины входа этот вопрос представляет собой классическую задачу « 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 .