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

Теоретическая модель вычислений

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

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

• 1 Предпосылки
  • 1.1 Детерминированная машина Тьюринга
• 2 Интуиция
  • 2.1 Разрешение множественных правил
• 3 Определение
  • 3.1 Альтернативные определения
• 4 Вычислительная эквивалентность с DTM
  • 4.1 DTM как частный случай NTM
  • 4.2 Моделирование DTM NTM
    • 4.2.1 Множественность состояний конфигурации
    • 4.2.2 Множественность лент
    • 4.2.3 Временная сложность и P в сравнении с NP
• 5 Ограниченный недетерминизм
• 6 Сравнение с квантовыми компьютерами
• 7 См. Также
• 8 Ссылки
• 9 Внешние ссылки

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

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

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

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

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

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

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

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

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

or

• Записать X, переместиться влево и остаться в состоянии 3.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

DTM-симуляция NTM

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

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

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

Множественность лент

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

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

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

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

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

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

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