Вопрос по недетерминированной машине Тьюринга

[SteelRend]

Здравствуйте. Пусть рассматриваются проблемы принадлежности, т.е. если $x$ - слово в некотором алфавите $\Sigma$, а $L$ - некоторое множество слов в этом этом алфавите, то нужно проверить $x \in L$ и выдать "ДА", если $x \in L$, и "НЕТ", если $x \notin L$. Например, пусть $L$ - множество представлений всех выполнимых формулы алгебры логики, тогда для слова $x$ нужно проверить, является ли оно представлением выполнимой формулы алгебры логики.

Как я читал, всякая недетерминированная МТ (алгоритм) работает в два этапа: 1) сначала она недетерминированно генерирует (угадывает) свидетельство (слово в некотором алфавите), позволяющее проверить принадлежность поданного ей на вход слова некоторому языку (т.е. делает предположение относительно принадлежности); 2) затем она, используя это свидетельство, осуществляет эту самую проверку принадлежности (т.е. проверяет сделанное предположение).

Например, недетерминированная МТ (алгоритм) для решения проблемы выполнимости булевых формул. На вход машине подаётся представление булевой формулы $F(x_1, x_2, ..., x_n)$ от $n$ булевых переменных, выполнимость которой нужно проверить, в виде слова в некотором алфавите (например, двоичном). Машина начинает свою работу с того, недетерминированно генерирует (угадывает) такую подстановку булевых значений $\alpha_1, \alpha_2, ..., \alpha_n$ в формулу $F$ вместо её $n$ переменных, что формула $F$ обращается в истинное высказывание, т.е. $F(\alpha_1, \alpha_2, ..., \alpha_n) = 1$. Для этого машина сначала недетерминированно угадывает подстановку вместо первой переменной, затем вместо второй и т.д. Затем машина проверяет правильность сделанного предположения: она вычисляет значение $F(\alpha_1, \alpha_2, ..., \alpha_n)$, и если набор значений действительно удовлетворяет формуле (обращает её в истинное высказывание), то машина принимает свой вход (т.е. говорит, что поданная ей на вход формула действительно является выполнимой).

При этом мы считаем, что если формула выполнима, то недетерминированная МТ (алгоритм) всегда верно угадывает подстановку. Теперь сам вопрос: а что, если на вход машине подаётся тождественно ложная формула (т.е. не выполнимая)? Правильно ли я понимаю, что в этом случае машина генерирует любую подстановку (всё равно, какую), вычисляет значение формулы на наборе значений из этой подстановки и, поскольку формула тождественно ложная, машина получает, что $F(\alpha_1, \alpha_2, ..., \alpha_n) = 0$, и поэтому она отклоняет свой вход (т.е. говорит, что поданная ей формула не является выполнимой)? И вообще, прошу разъяснить мне смысл сочетаний "недетерминированный выбор", "недетерминированное вычисление" и т.п.

[mihaild]

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

То, что можно эти выборы предварительно записать, и дальше работать детерменированно - отдельное утверждение.

[SteelRend]

Хорошо, а как она "узнаёт", в какое состояние ей нужно перейти и какое действие нужно совершить, когда у неё есть несколько вариантов дальнейших действий? Как тогда она вообще работает? Что есть недетерминированный выбор, недетерминированное вычисление?

[mihaild]

SteelRend, процитируйте более-менее строгие определения, и укажите, что именно в них непонятно. Переписывать учебники на форум смысла мало.

[SteelRend]

mihaild
НМТ это семёрка $ M = (Q, \Sigma, \Gamma, \delta, q_0, q_{accept}, q_{reject})$, где:
$Q, \Sigma, \Gamma, q_0, q_{accept}, q_{reject}$ имеют тот же смысл, что и в определении обычной МТ (множество внутренних состояний, входной алфавит, рабочий алфавит (входной алфавит есть подмножество рабочего алфавита), начальное состояние, допускающее состояние, отклоняющее состояние).
Функция переходов НМТ $\delta$ имеет вид $\delta: (Q-\{q_{accept}, q_{reject}\}) \times \Gamma \rightarrow P(Q \times \Gamma \times \{L, R, N\}) $

Формальное определение НМТ, где говорится, что функция её переходов есть отображение из множества пар вида $Q-\{q_{accept}, q_{reject}\} \times \Gamma $ в множество подмножеств множества троек вида $Q \times \Gamma \times \{L, R, N\}$ (т.е. одной паре $(p, Y), p \in (Q-\{q_{accept}, q_{reject}\}), Y \in \Gamma$ ставится в соответствие сразу множество троек $(q, X, Z), q \in Q, X \in \Gamma, Z \in \{L, R, N\}$, а не одна тройка, как в случае с детерминированной МТ) мне известно, мне непонятно как на самом деле работают недетерминированные алгоритмы, в своём заглавном сообщении я привёл одну из возможных интерпретаций/объяснений того, как они решают задачи (как я считал).

[mihaild]

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

[SteelRend]

А если более формально, каковы были бы действия недетерминированной МТ (алгоритма) для проверки выполнимости булевой формулы, если сама формула, представление которой записано на рабочей ленте машины, не является выполнимой? Как машина поймёт, что формулу (а именно, слово, записанное на её ленте и являющееся представлением/кодом такой формулы) нужно отклонить, какие действия она для совершит для этого? Как вообще строить недетерминированные алгоритмы?

-- 22.06.2018, 19:00 --

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

[mihaild]

SteelRend в сообщении #1321838 писал(а):

А если более формально, каковы были бы действия недетерминированной МТ (алгоритма) для проверки выполнимости булевой формулы, если сама формула, представление которой записано на рабочей ленте машины, не является выполнимой?

А если более формально, то нет понятия "действия МТ". Для детерменированной МТ довольно легко представить "физическое устройство", ее в некотором разумном смысле "реализующее". Для НМТ - скорее всего нельзя.
НМТ принимает слово $\leftrightarrow$ существует принимающий путь.

Если пытаться как-то "физически" реализовывать НМТ - то нужно либо перебирать все пути, либо в каком-то смысле создавать копии и пускать их работать параллельно.

[SteelRend]

mihaild
Ответьте тогда на вопрос,

SteelRend в сообщении #1321819 писал(а):

Правильно ли я понимаю, что в этом случае машина генерирует любую подстановку (всё равно, какую), вычисляет значение формулы на наборе значений из этой подстановки и, поскольку формула тождественно ложная, машина получает, что $F(\alpha_1, \alpha_2, ..., \alpha_n) = 0$, и поэтому она отклоняет свой вход (т.е. говорит, что поданная ей формула не является выполнимой)? И вообще, прошу разъяснить мне смысл сочетаний "недетерминированный выбор", "недетерминированное вычисление" и т.п.

НМТ начинает работу в начальном состоянии. На её ленте записано представление булевой формулы. МТ должна допустить или отклонить свой вход, выдать ответ "ДА" или "НЕТ". Формула тождественно ложная. Как НМТ поймёт, что её нужно отклонить? Что есть тогда недетерминированный алгоритм, недетерминированный выбор, недетерминированное вычисление?

mihaild в сообщении #1321840 писал(а):

А если более формально, то нет понятия "действия МТ"

Почему?

[mihaild]

SteelRend в сообщении #1321845 писал(а):

Как НМТ поймёт, что её нужно отклонить?

Понятие "НМТ поймет" не определено.

SteelRend в сообщении #1321845 писал(а):

Что есть тогда недетерминированный алгоритм?

SteelRend в сообщении #1321836 писал(а):

семёрка $ M = (Q, \Sigma, \Gamma, \delta, q_0, q_{accept}, q_{reject})$

Для детерменированной МТ ответы "да" и "нет" "равноправны" (это выражается, в частности, в том, что $P = co-P$). Для недетерменированной - вообще говоря, нет (например, скорее всего $NP \neq co-NP$).
Детерменированная МТ принимает слово, если, прочитав его, она в итоге приходит в принимающее состояние, и отвергает, если в отвергающее.
Недетерменированная принимает слово, если для каких-то выборов она приходит в принимающее состояние, и отвергает, если для любых выборов не приходит.
(и отвергающее состояния для НМТ можно вообще не фиксировать - пусть вместо завершения в нем она зацикливается)

SteelRend в сообщении #1321838 писал(а):

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

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

SteelRend в сообщении #1321838 писал(а):

Если бы мы действовали как недетерминированная МТ, то мы бы не только избегали тупиков, но и всегда выбирали бы маршрут минимальной длины, как будто бы зная заранее куда нужно идти (кто-то секретно сообщил нам маршрут).

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

[SteelRend]

mihaild в сообщении #1321848 писал(а):

Понятие "НМТ поймет" не определено

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

[mihaild]

SteelRend в сообщении #1321851 писал(а):

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

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

Например, возьмем описанную вами НМТ, проверяющую булеву формулу на выполнимость.
Корнем соответствующего дерева будет просто записанная исходная формула.
Затем оно начинает ветвиться: от корня отходят две ветви, соответствующие значениям первой переменной, каждая из них делится еще на две для второй переменной и т.д.
После $n$ ветвлений дальше в каждой из $2^n$ ветвей идет обычная детерменированная проверка "является ли данный набор выполняющим", заканчивающаяся, например, переходом в принимающее или отвергающее состояние.

[SteelRend]

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

[mihaild]

Да, можно так. Время вычисления в этом случае считается по самому короткому пути до принимающего листа.

[SteelRend]

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