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

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

¶Определение и формальная модель

Недетерминированная машина Тьюринга определяется как набор из семи компонентов:

• Q — конечное множество состояний;
• Σ — конечный входной алфавит (не содержит символа пробела);
• Γ — конечный алфавит ленты (включает Σ и символ пробела);
• δ — функция перехода, которая для каждой пары (состояние, символ) задаёт множество возможных действий: δ: Q × Γ → P(Q × Γ × {L, R}), где P — множество всех подмножеств;
• q₀ — начальное состояние (q₀ ∈ Q);
• q_accept — принимающее состояние (q_accept ∈ Q);
• q_reject — отвергающее состояние (q_reject ∈ Q, q_reject ≠ q_accept).

Ключевое отличие от детерминированной машины: функция δ возвращает не единственное действие, а множество возможных переходов. В процессе работы НМТ может «разветвляться» на несколько параллельных вычислительных путей.

¶Принцип работы

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

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

¶Связь с классами сложности

НМТ является фундаментальным инструментом для определения классов сложности:

• Класс NP (Nondeterministic Polynomial time) — множество задач, которые могут быть решены на НМТ за полиномиальное время (от длины входа). Классический пример: задача выполнимости булевых формул (SAT), задача коммивояжёра, задача о клике.
• Класс NEXP (Nondeterministic Exponential time) — задачи, решаемые на НМТ за экспоненциальное время.
• Класс NL (Nondeterministic Logarithmic space) — задачи, решаемые на НМТ с логарифмической памятью.

Важнейшая открытая проблема теории сложности — вопрос о равенстве классов P и NP. Если P = NP, то любая задача, проверяемая за полиномиальное время, может быть решена за полиномиальное время на детерминированной машине. Доказательство или опровержение этого равенства входит в список проблем тысячелетия.

¶Отличие от вероятностных машин

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

¶Реализация и моделирование

Хотя НМТ является абстрактной моделью, её можно моделировать на детерминированной машине. Основной метод — поиск в ширину или в глубину по дереву вычислений. Однако такое моделирование может потребовать экспоненциального времени (в худшем случае), так как количество путей может расти как 2^k, где k — число недетерминированных шагов.

Существуют также практические подходы к реализации недетерминизма:

• Backtracking (возврат) — алгоритм, который последовательно перебирает варианты и отсекает тупиковые ветви.
• Параллельные вычисления — если имеется достаточное количество процессоров, каждая ветвь может быть обработана независимо.
• Квантовые вычисления — квантовые компьютеры используют принцип суперпозиции, который позволяет одновременно находиться в нескольких состояниях, что напоминает недетерминизм, хотя и с существенными отличиями.

¶История и развитие

Понятие недетерминированной машины Тьюринга было введено в 1960-х годах в рамках развития теории сложности вычислений. Основоположниками считаются Джон фон Нейман, Стивен Кук, Ричард Карп и другие исследователи. В 1971 году Стивен Кук опубликовал работу, в которой сформулировал понятие NP-полноты и доказал, что задача SAT является NP-полной (теорема Кука — Левина). Это стало поворотным моментом в понимании связи между детерминированными и недетерминированными вычислениями.

¶Примеры задач, решаемых на НМТ

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

¶Критика и ограничения

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

¶Значение для информатики

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

¶Источники

• Ахо А., Хопкрофт Дж., Ульман Дж. «Построение и анализ вычислительных алгоритмов». — М.: Мир, 1979.
• Гэри М., Джонсон Д. «Вычислительные машины и труднорешаемые задачи». — М.: Мир, 1982.
• С. А. Кук. «The complexity of theorem-proving procedures». — Proceedings of the 3rd Annual ACM Symposium on Theory of Computing, 1971.
• М. Сипсер. «Введение в теорию сложности вычислений». — М.: МЦНМО, 2006.
• Ю. И. Журавлёв. «Теория сложности вычислений». — М.: Наука, 1988.