Машина Тьюринга недетерминированная: модель и сила

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

Что такое недетерминированный переход

Детерминированная машина Тьюринга задаётся функцией перехода $\delta: Q \times \Gamma \to Q \times \Gamma \times \{L, R\}$. По текущему состоянию и символу под головкой однозначно определяется тройка: новое состояние, записываемый символ и направление сдвига. Вычисление - это единственная цепочка конфигураций.

В недетерминированной машине Тьюринга функция перехода превращается в отношение:

$\delta: Q \times \Gamma \to \mathcal{P}(Q \times \Gamma \times \{L, R\}).$

Для пары «состояние, символ» задаётся не один ход, а множество допустимых ходов. На каждом шаге машина как бы «расщепляется»: для каждого варианта из $\delta(q, a)$ возникает своя ветвь вычисления. Формально НМТ - это семёрка $(Q, \Sigma, \Gamma, \delta, q_0, q_{accept}, q_{reject})$, отличающаяся от детерминированной только видом $\delta$.

Дерево вычислений и условие принятия

Удобно представлять работу НМТ деревом вычислений. Корень - начальная конфигурация, дети каждого узла - все конфигурации, в которые можно перейти за один шаг. Ниже - небольшой инструмент: задайте варианты ветвления и посмотрите, как разрастается дерево и каким будет вердикт.

Ключевое и часто непривычное правило: вход $w$ принимается, если в дереве вычислений существует хотя бы одна ветвь, ведущая в $q_{accept}$. Вход отвергается, только если все ветви заканчиваются отказом (или зацикливаются). Это асимметричное определение: для принятия достаточно одного удачного пути, для отказа нужна неудача по всем путям. Никакого «голосования большинством» здесь нет - модель ищет существование решения, а не его типичность.

Время работы недетерминированной машины

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

Важно, что это «время» не учитывает, сколько ветвей пришлось бы перебрать. Недетерминированная модель как будто бесплатно «угадывает» правильный ход на каждом шаге - отсюда альтернативная трактовка через схему «угадать и проверить» (guess-and-check). НМТ сначала недетерминированно записывает сертификат (догадку), а затем детерминированно проверяет его за полиномиальное время. Именно эта трактовка ведёт к классу сложности NP: язык лежит в $\mathrm{NP}$, если он распознаётся недетерминированной машиной Тьюринга за полиномиальное время.

Эквивалентность по разрешимости

Соблазнительно думать, что недетерминизм даёт принципиально больше вычислительной мощи. По разрешимости это не так. Любую недетерминированную машину Тьюринга можно сымитировать детерминированной: достаточно обходить дерево вычислений в ширину (BFS), последовательно проверяя все ветви глубины $1$, затем $2$ и так далее. Обход в ширину, а не в глубину, важен, чтобы не «провалиться» в бесконечную незавершающуюся ветвь, пропустив короткую принимающую.

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

Цена детерминированной симуляции

Симуляция недетерминированной машины детерминированной обходится дорого по времени. Если НМТ работает за время $t(n)$, а в каждой конфигурации число вариантов перехода ограничено константой $b$, то дерево вычислений содержит до $b^{t(n)}$ узлов. Детерминированный обход в ширину перебирает их все, поэтому верхняя оценка времени имитации - экспоненциальная: порядка $2^{O(t(n))}$.

Сократить эту экспоненту в общем случае никто не умеет - даже квантовые алгоритмы вроде факторизации по Шору дают выигрыш лишь для отдельных задач, а не для NP в целом. Открытый вопрос, можно ли вообще обойтись без экспоненциального взрыва для полиномиальных НМТ, - это и есть знаменитая проблема $\mathrm{P}$ против $\mathrm{NP}$. Если $\mathrm{P} = \mathrm{NP}$, то любое недетерминированное полиномиальное вычисление имеет детерминированный полиномиальный эквивалент; если нет - недетерминизм даёт реальный выигрыш для целого класса задач. Заметьте: по памяти аналогичный вопрос решён - теорема Сэвича даёт $\mathrm{NPSPACE} = \mathrm{PSPACE}$, то есть для пространства недетерминизм почти бесплатен.

Разбор схемы «угадать и проверить»

Покажем механику на задаче выполнимости (SAT). Дана булева формула $\varphi$ над переменными $x_1, \dots, x_n$, нужно решить, существует ли набор значений, при котором $\varphi$ истинна. Детерминированный перебор проверяет все $2^n$ наборов - экспонента. Недетерминированная машина действует иначе и за два этапа.

Сначала фаза угадывания: за $n$ недетерминированных шагов машина для каждой переменной $x_i$ выбирает значение $0$ или $1$. В дереве вычислений это даёт $2^n$ листьев - по одному на каждый возможный набор. Затем фаза проверки: вдоль выбранной ветви машина детерминированно подставляет угаданные значения в $\varphi$ и вычисляет её истинность за время, полиномиальное от размера формулы.

По определению принятия НМТ ответит «да» тогда и только тогда, когда хотя бы одна ветвь - то есть хотя бы один набор значений - делает формулу истинной. Это в точности определение выполнимости. Время работы НМТ здесь полиномиально: $n$ шагов на угадывание плюс полином на проверку. Так SAT оказывается в $\mathrm{NP}$, хотя детерминированного полиномиального алгоритма для него не известно. Эта же схема - «недетерминированно записать сертификат, детерминированно его проверить» - работает для раскраски графа, гамильтонова цикла и многих других переборных задач.

Где встречается на практике

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

Частые ошибки

• Считать, что НМТ решает неразрешимые задачи. Недетерминизм не обходит проблему остановки и не выходит за пределы тезиса Чёрча–Тьюринга - он эквивалентен детерминированной модели по классу вычислимых функций.
• Понимать принятие как «большинство ветвей принимает». Достаточно одной принимающей ветви; отказ требует неудачи по всем путям. Это существование, а не голосование.
• Путать «угадывание» с физической реализацией. Недетерминированный выбор - математическая идеализация, а не параллельные процессоры и не квантовый перебор: даже алгоритм Гровера ускоряет перебор лишь квадратично, а не «угадывает» ответ бесплатно, как НМТ.
• Обходить дерево в глубину при симуляции. DFS может застрять в бесконечной ветви и пропустить короткое принятие; корректна только обработка в ширину (по уровням).
• Отождествлять NP с «непереборными» задачами. $\mathrm{NP}$ - это класс языков с полиномиальной проверкой сертификата, а вопрос о реальной сложности перебора остаётся открытым ($\mathrm{P}$ vs $\mathrm{NP}$).

FAQ

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

Как связаны НМТ и класс NP? Язык принадлежит $\mathrm{NP}$, если он распознаётся недетерминированной машиной Тьюринга за полиномиальное время. Эквивалентно: для каждого слова из языка существует сертификат полиномиального размера, проверяемый детерминированно за полином.

Почему симуляция использует обход в ширину, а не в глубину? Чтобы гарантированно найти принимающую ветвь, если она конечна. Обход в глубину может бесконечно идти по незавершающейся ветви и так и не дойти до короткого принятия в другой части дерева; обход по уровням этого избегает.

Коротко

Недетерминированная машина Тьюринга обобщает функцию перехода до отношения: из одной конфигурации возможен набор ходов, а вход принимается, если хотя бы одна ветвь дерева вычислений достигает принимающего состояния. По множеству разрешимых задач она эквивалентна детерминированной модели - недетерминизм не нарушает тезис Чёрча–Тьюринга. Зато он переопределяет время работы (глубина одной ветви вместо перебора всех) и потому лежит в фундаменте класса NP и открытой проблемы $\mathrm{P}$ против $\mathrm{NP}$.