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

Эта статья требует дополнительных ссылок для проверки . Пожалуйста, помогите улучшить эту статью , добавив цитаты из надежных источников . Материал, не полученный от источника, может быть оспорен и удален. Найти источники:  «Недетерминированная машина Тьюринга»  -  новости  · газеты  · книги  · ученый  · JSTOR ( январь 2019 г. ) ( Узнайте, как и когда удалить это шаблонное сообщение )

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

НТМ иногда используются в мысленных экспериментах для изучения возможностей и ограничений компьютеров. Одной из наиболее важных открытых проблем теоретической информатики является проблема P vs. 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 \subseteq \left(Q\backslash 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) выход ^[1] и вместо него вставляют транзитивное замыкание любых желаемых стационарных переходов. ${\displaystyle \left(Q\times \Sigma \times \{-1,0,+1\}\right)}$

Некоторые авторы добавляют явное состояние отклонения ^[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 [ править ]

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

Универсальность [ править ]

В 2021 году Стивен Вольфрам предположил, что простейшей недетерминированной машине Тьюринга для достижения универсальности может потребоваться только 1 состояние и 2 цвета . ^[4] Возможно, универсальный набор правил только с одним состоянием показан на изображении справа. В этом смысле, поскольку машина имеет только одно состояние, это немного больше, чем недетерминированный конечный автомат с бесконечной памятью. Однако вычисления, необходимые для кодирования начального состояния и декодирования набора возможных результатов, могут быть настолько исчерпывающими, что лишают такую ​​систему права считаться универсальной в самом строгом смысле. Вольфрам сравнил NTM с некоторыми особенностями моделей, исследованных в Wolfram Physics Project . ^[4] В своей книгеНовый вид науки. Вольфрам выдвинул классическую гипотезу о самой маленькой универсальной детерминированной машине Тьюринга: трехсимвольной машине Тьюринга с двумя состояниями , которая позже оказалась универсальной.

Ограниченный недетерминизм [ править ]

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

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

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

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

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

См. Также [ править ]

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

Ссылки [ править ]

Дополнительная литература [ править ]

• Гарри Р. Льюис , Христос Пападимитриу (1981). Элементы теории вычислений (1-е изд.). Прентис-Холл. ISBN 0-13-273417-6. Раздел 4.6: Недетерминированные машины Тьюринга, стр. 204–211.
• Джон К. Мартин (1997). Введение в языки и теорию вычислений (2-е изд.). Макгроу-Хилл. ISBN 0-07-040845-9. Раздел 9.6: Недетерминированные машины Тьюринга, стр. 277–281.
• Христос Пападимитриу (1993). Вычислительная сложность (1-е изд.). Эддисон-Уэсли. ISBN 0-201-53082-1. Раздел 2.7: Недетерминированные машины, стр. 45–50.
• Вольфрам, Стивен (2002). Новый вид науки . Wolfram Media, Inc., стр. 967–968. ISBN 1-57955-008-8.

Внешние ссылки [ править ]

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