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

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

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

Фон

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

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

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

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

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

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

Интуиция

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

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

или

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

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

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

Определение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

DTM-моделирование NTM

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

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

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

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

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

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

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

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

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

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

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

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

См. также

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

Ссылки

^ Гэри, Майкл Р.; Дэвид С. Джонсон (1979). Компьютеры и трудноразрешимые проблемы: Руководство по теории NP-полноты . У. Х. Фриман. ISBN 0-7167-1045-5 .
^ Эриксон, Джефф. «Недетерминированные машины Тьюринга» (PDF) . Университет Иллинойса Урбана-Шампейн . Проверено 7 апреля 2019 г.
^ Льюис, Гарри Р .; Пападимитриу, Христос (1981). «Раздел 4.6: Недетерминированные машины Тьюринга». Элементы теории вычислений (1-е изд.). Энглвуд Клиффс, Нью-Джерси: Прентис-Холл. стр. 204–211. ISBN 978-0132624787 .
^ Часто задаваемые вопросы по борьбе с шумихой вокруг квантовых компьютеров Orion , Скотт Ааронсон .
^ Тушарова, Тереза (2004). «Квантовые классы сложности». arXiv : cs/0409051 . .

Общий

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

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

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

[GJ-1] Гэри, Майкл Р.; Дэвид С. Джонсон (1979). Компьютеры и трудноразрешимые проблемы: Руководство по теории NP-полноты . У. Х. Фриман. ISBN 0-7167-1045-5 .

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

[3] Льюис, Гарри Р .; Пападимитриу, Христос (1981). «Раздел 4.6: Недетерминированные машины Тьюринга». Элементы теории вычислений (1-е изд.). Энглвуд Клиффс, Нью-Джерси: Прентис-Холл. стр. 204–211. ISBN 978-0132624787 .

[4] Часто задаваемые вопросы по борьбе с шумихой вокруг квантовых компьютеров Orion , Скотт Ааронсон .

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

[1]

[2]

[3]

[4]

[5]