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

Материал из Википедии — свободной энциклопедии

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

Содержание

1 Описание
2 Определение
3 Эквивалентность с ДМТ
4 См. также
- 4.1 Другие абстрактные исполнители и формальные системы вычислений
5 Ссылки

[править] Описание

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

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

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

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

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

[править] Определение

Более формально, недетерминированная машина Тьюринга — это шестёрка объектов $M=(Q, \Sigma, \iota, \sqcup, A, \delta)$ , где

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

[править] Эквивалентность с ДМТ

Интуитивно кажется, что НМТ более мощные, чем ДМТ, так как они выполняют несколько возможных вычислений сразу, требуя только, чтобы хоть одно из них заканчивалось в допускающем состоянии. Однако любой язык, допускающийся НМТ, также допускается ДМТ: ДМТ может моделировать любой переход НМТ, делая многократные копии состояния, если встречается неоднозначность, как это делает многозадачная операционная система.

Очевидно, что это моделирование требует значительно больше времени. Насколько больше — неизвестно. В частном случае ограничения по времени в виде полинома от длины входа этот вопрос представляет собой классическую задачу «P = NP» (см. классы сложности P и NP).

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