В теоретической информатике недетерминированная машина Тьюринга ( NTM ) — это теоретическая модель вычислений, чьи управляющие правила определяют более одного возможного действия в некоторых заданных ситуациях. То есть следующее состояние NTM не полностью определяется ее действием и текущим символом, который она видит, в отличие от детерминированной машины Тьюринга .
NTM иногда используются в мысленных экспериментах для изучения возможностей и ограничений компьютеров. Одной из важнейших открытых проблем в теоретической информатике является проблема P против NP , которая (среди других эквивалентных формулировок) касается вопроса о том, насколько сложно смоделировать недетерминированное вычисление с помощью детерминированного компьютера.
По сути, машина Тьюринга представляется как простой компьютер, который считывает и записывает символы по одному на бесконечной ленте, строго следуя набору правил. Он определяет, какое действие он должен выполнить следующим в соответствии со своим внутренним состоянием и тем, какой символ он в данный момент видит . Примером одного из правил машины Тьюринга может быть: «Если вы находитесь в состоянии 2 и видите „A“, то измените его на „B“, переместитесь влево и переключитесь в состояние 3».
В детерминированной машине Тьюринга (DTM) набор правил предписывает выполнить не более одного действия в любой заданной ситуации.
Детерминированная машина Тьюринга имеет функцию перехода , которая для заданного состояния и символа под головкой ленты определяет три вещи:
Например, символ X на ленте в состоянии 3 может заставить DTM записать символ Y на ленте, переместить головку на одну позицию вправо и переключиться в состояние 5.
В отличие от детерминированной машины Тьюринга, в недетерминированной машине Тьюринга ( NTM ) набор правил может предписывать более одного действия для любой заданной ситуации. Например, X на ленте в состоянии 3 может позволить NTM:
или
Как NTM «знает», какое из этих действий она должна предпринять? Есть два способа взглянуть на это. Один из них — сказать, что машина — «самый удачливый из возможных угадывателей»; она всегда выбирает переход, который в конечном итоге приводит к принимающему состоянию, если такой переход есть. Другой — представить, что машина « ветвится » на множество копий, каждая из которых следует одному из возможных переходов. В то время как DTM имеет единственный «путь вычислений», по которому она следует, NTM имеет «дерево вычислений». Если хотя бы одна ветвь дерева останавливается с условием «принять», NTM принимает ввод.
Недетерминированную машину Тьюринга можно формально определить как шестиэлементную , где
Отличие от стандартной (детерминированной) машины Тьюринга заключается в том, что для детерминированных машин Тьюринга отношение перехода является функцией, а не просто отношением.
Конфигурации и отношение выходов на конфигурациях, которое описывает возможные действия машины Тьюринга с учетом любого возможного содержимого ленты, такие же, как и для стандартных машин Тьюринга, за исключением того, что отношение выходов больше не является однозначным. (Если машина детерминирована, все возможные вычисления являются префиксами одного, возможно бесконечного, пути.)
Входные данные для NTM предоставляются таким же образом, как и для детерминированной машины Тьюринга: машина запускается в конфигурации, в которой головка ленты находится на первом символе строки (если таковой имеется), в противном случае лента полностью пуста.
NTM принимает входную строку тогда и только тогда, когда хотя бы один из возможных вычислительных путей, начинающихся с этой строки, переводит машину в принимающее состояние. При моделировании множества ветвящихся путей NTM на детерминированной машине мы можем остановить всю симуляцию, как только любая ветвь достигнет принимающего состояния.
Поскольку NTM — это математическая конструкция, используемая в основном в доказательствах, существует множество незначительных вариаций определения, но все эти вариации допускают эквивалентные языки.
Движение головы в выходных данных отношения перехода часто кодируется численно, а не с помощью букв для представления перемещения головы влево (-1), неподвижно (0) и вправо (+1); давая выходную функцию перехода . Обычно выходной сигнал неподвижного (0) состояния опускается, [1] и вместо этого вставляется транзитивное замыкание любых желаемых стационарных переходов.
Некоторые авторы добавляют явное состояние отклонения , [2] , которое заставляет NTM останавливаться без принятия. Это определение все еще сохраняет асимметрию, что любая недетерминированная ветвь может принять, но каждая ветвь должна отклонить, чтобы строка была отклонена.
Любая вычислительная задача, которую можно решить с помощью DTM, может быть решена и с помощью NTM, и наоборот. Однако считается, что в общем случае временная сложность может быть разной.
NTM включают DTM как особые случаи, поэтому каждое вычисление, которое может быть выполнено с помощью DTM, может быть выполнено и эквивалентной NTM.
Может показаться, что NTM мощнее DTM, поскольку они могут допускать деревья возможных вычислений, возникающих из одной и той же начальной конфигурации, принимая строку, если любая ветвь в дереве принимает ее. Однако возможно моделировать NTM с помощью DTM, и на самом деле это можно сделать более чем одним способом.
Один из подходов заключается в использовании DTM, конфигурации которой представляют собой несколько конфигураций NTM, а работа DTM заключается в посещении каждой из них по очереди, выполнении одного шага при каждом посещении и создании новых конфигураций всякий раз, когда отношение перехода определяет несколько продолжений.
Другая конструкция имитирует NTM с помощью 3-ленточных DTM, из которых первая лента всегда содержит исходную входную строку, вторая используется для имитации конкретного вычисления NTM, а третья кодирует путь в вычислительном дереве NTM. [3] 3-ленточные DTM легко имитируются с помощью обычного одноленточного DTM.
Во второй конструкции построенный DTM эффективно выполняет поиск в ширину дерева вычислений NTM, посещая все возможные вычисления NTM в порядке увеличения длины, пока не найдет приемлемое. Таким образом, длина приемлемого вычисления DTM, как правило, экспоненциальна по длине кратчайшего приемлемого вычисления NTM. Считается, что это общее свойство симуляций NTM с помощью DTM. Проблема P = NP , самый известный нерешенный вопрос в информатике, касается одного случая этой проблемы: обязательно ли каждая задача, решаемая NTM за полиномиальное время, также решаема DTM за полиномиальное время.
NTM обладает свойством ограниченного недетерминизма. То есть, если NTM всегда останавливается на заданной входной ленте T , то он останавливается через ограниченное число шагов и, следовательно, может иметь только ограниченное число возможных конфигураций.
Поскольку квантовые компьютеры используют квантовые биты , которые могут находиться в суперпозициях состояний, а не обычные биты, иногда возникает ошибочное представление о том, что квантовые компьютеры являются NTM. [4] Однако эксперты полагают (хотя это не доказано), что мощность квантовых компьютеров на самом деле несопоставима с мощностью NTM; то есть, вероятно, существуют проблемы, которые NTM может эффективно решить, а квантовый компьютер не может, и наоборот. [5] [ нужен лучший источник ] В частности, вероятно, что NP-полные задачи решаются NTM, но не квантовыми компьютерами за полиномиальное время.
Интуитивно говоря, хотя квантовый компьютер действительно может находиться в состоянии суперпозиции, соответствующем всем возможным вычислительным ветвям, выполненным одновременно (аналогично NTM), окончательное измерение сожмет квантовый компьютер в случайно выбранную ветвь. Эта ветвь тогда, в общем случае, не представляет искомое решение, в отличие от NTM, которому разрешено выбирать правильное решение среди экспоненциально большого числа ветвей.
