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

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

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

Фон

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

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

В детерминированной машине Тьюринга (DTM) набор правил предписывает не более одного действия, которое должно быть выполнено для любой данной ситуации.

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

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

Например, X на ленте в состоянии 3 может заставить DTM записать Y на ленте, переместить головку на одну позицию вправо и переключиться в состояние 5.

Интуиция

Сравнение детерминированных и недетерминированных вычислений

В отличие от детерминированной машины Тьюринга, в недетерминированной машине Тьюринга ( NTM ) набор правил может предписывать более одного действия, которое должно быть выполнено для любой данной ситуации. Например, X на ленте в состоянии 3 может позволить NTM:

• Напишите Y, двигайтесь вправо и переключитесь в состояние 5

или

• Напишите X, двигайтесь влево и оставайтесь в состоянии 3.

Разрешение нескольких правил

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

Определение

Недетерминированную машину Тьюринга можно формально определить как набор из шести элементов , где ${\ Displaystyle M = (Q, \ Sigma, \ iota, \ sqcup, A, \ delta)}$

• ${\ displaystyle Q}$ конечный набор состояний
• ${\ displaystyle \ Sigma}$ конечный набор символов (ленточный алфавит)
• ${\ displaystyle \ iota \ in Q}$ это начальное состояние
• ${\ displaystyle \ sqcup \ in \ Sigma}$ это пустой символ
• ${\ displaystyle A \ substeq Q}$ это набор принимающих (конечных) состояний
• ${\ displaystyle \ delta \ substeq \ left (Q \ обратная косая черта A \ times \ Sigma \ right) \ times \ left (Q \ times \ Sigma \ times \ {L, S, R \} \ right)}$это отношение состояний и символов, называемое отношением перехода . движение влево, отсутствие движения и движение вправо.${\ displaystyle L}$${\ displaystyle S}$${\ displaystyle R}$

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

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

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

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

Альтернативные определения

В качестве математической конструкции, используемой в основном в доказательствах, существует множество незначительных вариаций определения NTM, но все эти вариации допускают эквивалентные языки.

Движение головы в выходных данных отношения перехода часто кодируется численно вместо использования букв для обозначения перемещения головы влево (-1), неподвижно (0) и вправо (+1); давая выход функции перехода . Обычно опускают стационарный (0) выход и вместо этого вставляют транзитивное замыкание любых желаемых стационарных переходов. ${\ displaystyle \ left (Q \ times \ Sigma \ times \ {- 1,0, + 1 \} \ right)}$

Некоторые авторы добавляют явное состояние отклонения , которое заставляет NTM останавливаться без принятия. Это определение по-прежнему сохраняет асимметрию, которую может принять любая недетерминированная ветвь, но каждая ветвь должна отклонить, чтобы строка была отклонена.

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

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

DTM как частный случай NTM

NTM включают DTM как особые случаи, поэтому каждое вычисление, которое может быть выполнено с помощью DTM, также может выполняться эквивалентным NTM.

ЦМР моделирование НТМ

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

Множественность состояний конфигурации

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

Кратность лент

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

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

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

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

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

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

Предполагаемая форма круга задач, решаемых квантовыми компьютерами за полиномиальное время (BQP). Обратите внимание, что на рисунке предполагается и . Если это не так, то фигура должна выглядеть иначе.${\ Displaystyle {\ mathsf {P}} \ neq {\ mathsf {NP}}}$${\ Displaystyle {\ mathsf {NP}} \ neq {\ mathsf {PSPACE}}}$

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

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

Смотрите также

• Вероятностная машина Тьюринга

использованная литература

• Мартин, Джон С. (1997). «Раздел 9.6: Недетерминированные машины Тьюринга». Введение в языки и теорию вычислений (2-е изд.). Макгроу-Хилл. С. 277–281. ISBN 978-0073191461.
• Пападимитриу, Христос (1993). «Раздел 2.7: Недетерминированные машины». Вычислительная сложность (1-е изд.). Эддисон-Уэсли. С. 45–50. ISBN 978-0201530827.

внешние ссылки

• C ++ Simulator of a Nondeterministic Multitape Machine Turing Machine (бесплатное программное обеспечение).
• C ++ Симулятор недетерминированной многоленточной машины Тьюринга ссылка для скачивания с sourceforge.net