Введение

Теоретическая модель вычислений

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

Предыстория

По сути, машина Тьюринга представляется простым компьютером, который по одному символу читает и записывает информацию на бесконечной ленте, строго следуя заданному набору правил. Она определяет следующее действие, основываясь на своем внутреннем состоянии и символе, который она видит в данный момент. Например, одно из правил машины Тьюринга может быть таким: "Если ты находишься в состоянии 2 и видишь символ 'А', замени его на 'B', передвинься влево и перейди в состояние 3".

Решение многочисленных правил

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

Вычислительная эквивалентность с DTM

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

DTM как особый случай NTM

НДМА включают ДМТ как частные случаи, поэтому любое вычисление, которое может быть выполнено ДМТ, может быть выполнено и эквивалентным НДМА.

Моделирование DTM NTM

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

Многообразие состояний конфигурации

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

Многообразие лент

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

Временная сложность и P против NP

Во второй конструкции, построенный DTM эффективно осуществляет поиск в ширину по дереву вычислений NTM, просматривая все возможные вычисления NTM в порядке возрастания длины, пока не найдет принимающее вычисление. Следовательно, длина принимающего вычисления DTM, как правило, экспоненциально зависит от длины кратчайшего принимающего вычисления NTM. Считается, что это общее свойство для моделирования NTM с помощью DTM. Проблема P = NP, наиболее известная нерешенная задача в информатике, касается частного случая этой проблемы: является ли каждая задача, разрешимая NTM за полиномиальное время, также разрешимой DTM за полиномиальное время.

Ограниченный недетерминизм

НТМ обладает свойством ограниченного недетерминизма. Это означает, что если НТМ всегда останавливается для заданной входной ленты T, то он останавливается за конечное число шагов и, следовательно, может иметь лишь конечное число возможных конфигураций.

Сравнение с квантовыми компьютерами

Поскольку квантовые компьютеры используют квантовые биты, которые могут находиться в суперпозиции состояний, а не в обычных битах, иногда возникает ошибочное мнение, что квантовые компьютеры являются недетерминированными машинами Тьюринга (НТМ). Однако эксперты полагают (хотя это и не доказано), что вычислительная мощность квантовых компьютеров на самом деле не сопоставима с мощностью НТМ; то есть, вероятно, существуют задачи, которые НТМ может эффективно решать, а квантовый компьютер – нет, и наоборот. В частности, вероятно, что NP-полные задачи разрешимы НТМ, но не квантовыми компьютерами за полиномиальное время. Интуитивно, хотя квантовый компьютер действительно может находиться в суперпозиционном состоянии, соответствующем одновременному выполнению всех возможных вычислительных ветвей (подобно НТМ), конечное измерение приводит к коллапсу квантового компьютера в случайно выбранную ветвь. Эта ветвь, как правило, не представляет собой искомое решение, в отличие от НТМ, которой разрешено выбрать правильное решение из экспоненциально большого числа ветвей.