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


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

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

Содержание

Описание

Детерминированная машина Тьюринга имеет функцию перехода, которая по комбинации текущего состояния и символа на ленте определяет три вещи: символ, который будет записан на ленте, направление смещения головки по ленте и новое состояние конечного автомата. Например, X на ленте в состоянии 3 однозначно определяет переход в состояние 4, запись на ленту символа Y и перемещение головки на одну позицию влево.

В случае недетерминированной машины Тьюринга, комбинация текущего состояния автомата и символа на ленте может допускать несколько переходов. Например, X на ленте и состояние 3 допускает как состояние 4 с записью на ленту символа Y и смещением головки вправо, так и состояние 5 с записью на ленту символа Z и смещением головки влево.

Как НМТ «узнаёт», какой из возможных путей приведёт в допускающее состояние? Есть два способа это представить.

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

То есть в отличие от ДМТ, которая имеет единственный «путь вычислений», НМТ имеет «дерево вычислений» (в общем случае — экспоненциальное число путей). Говорят, что НМТ допускает входные данные, если какая-нибудь ветвь этого дерева останавливается в допускающем состоянии, иначе НМТ входные данные не допускает. (Таким образом, ответы «ДА» и «НЕТ» в случае недетерминированных вычислений несимметричны.)

Определение

Более формально, недетерминированная машина Тьюринга — это шестёрка объектов M=(Q, \Sigma, \iota, \sqcup, A, \delta), где

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

Эквивалентность с ДМТ

Интуитивно кажется, что НМТ более мощные, чем ДМТ, так как они выполняют несколько возможных вычислений сразу, требуя только, чтобы хоть одно из них заканчивалось в допускающем состоянии. Однако любой язык, допускающийся НМТ, также допускается ДМТ: ДМТ может моделировать любой переход НМТ, делая многократные копии состояния, если встречается неоднозначность.

Очевидно, что это моделирование требует значительно больше времени. Насколько больше — неизвестно. В частном случае ограничения по времени в виде полинома от длины входа этот вопрос представляет собой классическую задачу «P = NP» (см. классы сложности P и NP).

Класс алгоритмов, выполняемых за полиномиальное время на недетерминированных машинах Тьюринга, называется классом NP.

Пример

Рассмотрим задачу проверки того что данное b-разрядное целое число N (2b-1≤N<2b) является составным. Тогда b — длина входных данных, по отношению к которому рассматривается время вычисления. Ответ «ДА» — число составное и «НЕТ» — простое. Эта задача является комплементарной к тесту на простоту.

Недетерминированный алгоритм для этой задачи может быть например следующий:

  • Выбрать недетерминированно целое число m такое что 1<m<N.
  • Разделить нацело N на m, остаток обозначим через a.
  • Если a=0 выдать ответ «ДА» (m тогда — делитель N), иначе выдать ответ «НЕТ».

(Алгоритм написан не непосредственно в виде определения машины Тьюринга.)

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

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

Если моделировать этот алгоритм на детерминированной машине Тьюринга, пробуя по очереди все возможные варианты, требуется проверить N-2=O(2b) ветвей. Таким образом общее время вычислений будет O(b22b) шагов, что представляет собой уже экспоненциальное время, которое существенно больше чем полиномиальное время. Таким образом этот алгоритм не попадает в класс P. (Однако, могут быть применены другие, более быстрые алгоритмы для этой задачи, которые работают за полиномиальное время, и таким образом задача попадает в класс P.)

См также:

  • Тест на простоту про более быстрые алгоритмы решения данной задачи
  • P = NP про сравнение классов P и NP

См. также

Другие абстрактные исполнители и формальные системы вычислений

Ссылки


Wikimedia Foundation. 2010.

Смотреть что такое "Недетерминированная машина Тьюринга" в других словарях:

  • недетерминированная машина Тьюринга — — [[http://www.rfcmd.ru/glossword/1.8/index.php?a=index d=23]] Тематики защита информации EN non deterministic Turing machine …   Справочник технического переводчика

  • Машина Тьюринга для умножения чисел — Машина Тьюринга (МТ) абстрактный исполнитель (абстрактная вычислительная машина). Была предложена Аланом Тьюрингом в 1936 году для формализации понятия алгоритма. Машина Тьюринга является расширением конечного автомата и, согласно тезису Чёрча… …   Википедия

  • Машина тьюринга — (МТ) абстрактный исполнитель (абстрактная вычислительная машина). Была предложена Аланом Тьюрингом в 1936 году для формализации понятия алгоритма. Машина Тьюринга является расширением конечного автомата и, согласно тезису Чёрча Тьюринга, способна …   Википедия

  • Машина Тьюринга — Художественное представление машины Тьюринга Машина Тьюринга (МТ)  абстрактный исполнитель (абстрактная вычислительная машина). Была предложена Аланом Тьюрингом в 1936 году для формализации понятия алгоритма …   Википедия

  • Детерминированная машина Тьюринга — Машина Тьюринга (МТ) абстрактный исполнитель (абстрактная вычислительная машина). Была предложена Аланом Тьюрингом в 1936 году для формализации понятия алгоритма. Машина Тьюринга является расширением конечного автомата и, согласно тезису Чёрча… …   Википедия

  • Вероятностная машина Тьюринга — Машина Тьюринга Варианты машин Универсальная машина Тьюринга Квантовая машина Тьюринга en:Read only Turing machine en:Read only right moving Turing Machines Вероятностная машина Тьюринга Не …   Википедия

  • Квантовая машина Тьюринга — Машина Тьюринга Варианты машин Универсальная машина Тьюринга Квантовая машина Тьюринга en:Read only Turing machine en:Read only right moving Turing Machines Вероятностная машина Тьюринга Неде …   Википедия

  • Тьюринга машина — Машина Тьюринга (МТ) абстрактный исполнитель (абстрактная вычислительная машина). Была предложена Аланом Тьюрингом в 1936 году для формализации понятия алгоритма. Машина Тьюринга является расширением конечного автомата и, согласно тезису Чёрча… …   Википедия

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

  • Вычислительная сложность — В информатике и теории алгоритмов вычислительная сложность алгоритма это функция, определяющая зависимость объёма работы, выполняемой некоторым алгоритмом, от размера входных данных. Раздел, изучающий вычислительную сложность, называется теорией… …   Википедия


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.