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

Машина Тьюринга
Варианты машин
Универсальная машина Тьюринга Квантовая машина Тьюринга en:Read-only Turing machine en:Read-only right moving Turing Machines Вероятностная машина Тьюринга Недетерминированная машина Тьюринга en:Multi-track Turing machine en:Turing machine equivalents en:Turing machine examples en:Turing Machine simulator Wolfram's 2-state 3-symbol.. Машина Поста

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

Описание

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

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

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

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

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

Определение

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

• $Q$ — конечное множество состояний
• $\Sigma$ — конечное множество символов (алфавит ленты)
• $\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.

Пример

Рассмотрим задачу проверки того что данное 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.)

См также:

• Тест на простоту про более быстрые алгоритмы решения данной задачи
• P = NP про сравнение классов P и NP

См. также

• Машина Тьюринга
• Вероятностная машина Тьюринга
• Универсальная машина Тьюринга
• Теория алгоритмов
• Конечный автомат

Другие абстрактные исполнители и формальные системы вычислений

• Машина Тьюринга
• Алгоритмы Маркова (продукционное программирование)
• Brainfuck (императивное программирование)
• Машина Поста (автоматное программирование)
• Лямбда-исчисление (функциональное программирование)

Ссылки

• Определения и примеры машин Тьюринга
• Карпов Ю.П. Теория автоматов ISBN 5-318-00537-3
• Программная система моделирования работы машины Тьюринга