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

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

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

Фон

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

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

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

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

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

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

Интуиция

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

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

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

или же

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

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

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

Определение

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

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

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

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

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

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

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

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

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

Некоторые авторы добавляют явное отклонять государственный,^[2]что приводит к остановке NTM без принятия. Это определение все еще сохраняет асимметрию, что любой недетерминированная ветвь может принимать, но каждый ветка должна отклоняться, чтобы строка была отклонена.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Предполагаемая форма круга проблем решаемая квантовыми компьютерами за полиномиальное время (BQP). Обратите внимание, что рисунок предполагает

{displaystyle {mathsf {P}} eq {mathsf {NP}}}

и

{displaystyle {mathsf {NP}} eq {mathsf {PSPACE}}}

. Если это не так, фигура должна выглядеть иначе.

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

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

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

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

внешняя ссылка

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

[GJ-1] Garey, Michael R .; Дэвид С. Джонсон (1979). Компьютеры и непреодолимость: руководство по теории NP-полноты. В. Х. Фриман. ISBN 0-7167-1045-5.

[jeffe-2] Эриксон, Джефф. «Недетерминированные машины Тьюринга» (PDF). U. Illinois Урбана-Шампейн. Получено 2019-04-07.

[3] Элементы теории вычислений, Гарри Р. Льюис и Христос Х. Пападимитриу, Прентис-Холл, Энглвуд Клиффс, Нью-Джерси, 1981, ISBN 0-13-273417-6, стр. 206–211

[4] Часто задаваемые вопросы о квантовом компьютере Orion Anti-Hype, Скотт Ааронсон.

[5] Тушарова, Тереза (2004). «Классы квантовой сложности». arXiv:cs / 0409051..

[1]

[2]

[3]

[4]

[5]