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

[mihaild]

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

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

которую как раз-таки, в общем случае, не получается сгенерировать (угадать, получить от несуществующего в реальности оракула и т.д.) за полиномиальное время?

Более точно - неизвестно, можно ли ее сгенерировать за полиномиальное время (вопрос об этой возможности эквивалентен P vs NP).

[SteelRend]

mihaild
Спасибо за разъяснения. Если ещё появятся вопросы по этой теме, я их здесь спрошу.

[george66]

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

[iifat]

Насколько я помню, недетерминированная машина таки вообще никак не «действует». Это чисто математическое понятие. Есть граф состояний и переходов. Строка допускается, если есть некий путь в графе, не хочу вспоминать точно, какой.
Поиск этого пути — задача отдельная.

[SteelRend]

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

Цитата:

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

Т.е. детерминированная машина всё же должна производить вычисления (пусть это будет человек, выполняющий это вычисление), и я хотел узнать, как можно представить процесс решения вопроса $x \in L$ недетерминированной машиной (вернее, как она проверяет непринадлежность), что понимается под недетерминированным выбором, и например, как понимать фразу "Для некоторой формулы $F$ над $n$ булевыми переменными $x_1, x_2, ..., x_n$ машина угадывает какой-либо из возможных наборов $\alpha_1, \alpha_2, ..., \alpha_n$ значений переменных $x_1, x_2, ..., x_n$".

[mihaild]

Хорошего способа нет.
Более того, если не ставить ограничения на время работы, то класс языков, распознаваемых недетерменированными машинами, шире класса языков, распознаваемых детерменированными. Например, язык "номера останавливающихся машин Тьюринга" не распознается никакой детерменированной МТ, но распознается недетерменированной. Так что если не ставить ограничения на время работы, то вычислимо определить, что данное слово отвергается данной НМТ, вообще нельзя.

[SteelRend]

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

Более того, если не ставить ограничения на время работы, то класс языков, распознаваемых недетерменированными машинами, шире класса языков, распознаваемых детерменированными. Например, язык "номера останавливающихся машин Тьюринга" не распознается никакой детерменированной МТ, но распознается недетерменированной

Этот момент мне не совсем понятен. Пусть имеется язык кодов номеров всех машин, которые всегда останавливаются. Детерминированная машина по заданному номеру $i$ (коду этого номера, например в двоичном алфавите) строит представление (код) МТ с $i$-ым номером относительно лексикографического порядка, и начинает применять входы к этой машине в лексикографическом порядке -- сначала пробует пустое слово, затем 0, затем 1, затем 00 и т.д. Поскольку слов в двоичном алфавите бесконечное множество, то машина никогда не перепробует их все, и следовательно, никогда не остановится, следовательно, никогда не допустит свой вход (даже если номер, поданный ей на вход, действительно есть номер МТ, которая всегда останавливается). Недетерминированной машине при проверке останова придётся неограниченно много раз делиться (она создаёт отдельную ветвь для каждого слова $x \in \Sigma^\star$, генерирует это слово и проверяет останов машины с поданным ей на вход номером), но это значит, что она не обладает конечным описанием и, по-видимому, вообще не должна считаться алгоритмом. И как же теорема "класс языков, распознаваемых недетерминированнми МТ и класс языков, распознаваемых детерминированными МТ, совпадают"?

[mihaild]

Я неудачно выразился - "останавливающаяся МТ" в данном случае значит "МТ, останавливающаяся на пустом входе". Довольно легко сделать детерменированную МТ, которая останавливается на номерах МТ, останавливающихся на пустом входе, и не останавливающуюся на остальных.
И эта МТ распознает язык из номеров МТ, останавливающихся на пустом входе, если ее рассматривать как недетерменированную. А детерменированной, распознающей этот язык, не существует.

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

И как же теорема "класс языков, распознаваемых недетерминированной МТ и класс языков, распознаваемых детерминированной МТ, совпадают"?

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

[iifat]

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

Т.е. детерминированная машина всё же должна производить вычисления

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

-- 23.06.2018, 12:47 --

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

И как же теорема "класс языков, распознаваемых недетерминированнми МТ и класс языков, распознаваемых детерминированными МТ, совпадают"?

Ссылочку можно? Для автоматов с магазинной памятью это не так, точно помню, а реализовать такой автомат на МТ, как понимаю, можно.

[Xaositect]

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

Я неудачно выразился - "останавливающаяся МТ" в данном случае значит "МТ, останавливающаяся на пустом входе". Довольно легко сделать детерменированную МТ, которая останавливается на номерах МТ, останавливающихся на пустом входе, и не останавливающуюся на остальных.
И эта МТ распознает язык из номеров МТ, останавливающихся на пустом входе, если ее рассматривать как недетерменированную. А детерменированной, распознающей этот язык, не существует.

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

И как же теорема "класс языков, распознаваемых недетерминированной МТ и класс языков, распознаваемых детерминированной МТ, совпадают"?

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

Давайте правильно употреблять термины. Распознавание языков подразумевает, что бесконечных вычислительных путей не существует.

Недетерминированная машина, которая распознает язык, должна иметь 2 терминальных состояния - YES и NO. И для того, чтобы распознавать язык $L$, любой вычислительный путь на любом слове должен быть конечным. При этом $x\in L$ тогда и только тогда, когда на входе $x$ существует вычислительный путь, приводящий в состояние YES. Соответственно, если $x \notin L$, все пути должны приводить в состояние NO.

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

iifat в сообщении #1321946 писал(а):

Ссылочку можно?

Lewis, Papadimitriou "Elements of the theory of computation", параграф 4.5.

[iifat]

Xaositect в сообщении #1321952 писал(а):

Недетерминированная машина, которая распознает язык, должна иметь 2 терминальных состояния - YES и NO

Ну, в вашем источнике рассматривают и полураспознавание (не знаю, как бы перевести).

Xaositect в сообщении #1321952 писал(а):

любой вычислительный путь на любом слове должен быть конечным

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

[Xaositect]

iifat в сообщении #1321975 писал(а):

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

А для полураспознавания будет то же самое, множество языков, полураспознаваемых недерминированными машинами, совпадает с множеством языков, полураспознаваемых детерминированными.

[SteelRend]

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

Я неудачно выразился - "останавливающаяся МТ" в данном случае значит "МТ, останавливающаяся на пустом входе". Довольно легко сделать детерменированную МТ, которая останавливается на номерах МТ, останавливающихся на пустом входе, и не останавливающуюся на остальных.

Пустой вход -- имеется в виду пустой язык $L_{\emptyset} = \emptyset$ или пустое слово $\lambda$? В случае пустого языка проблема остаётся такой же, ведь машине нужно будет проверить, что каждое слово $x \in \Sigma^{\star}$ отклоняется машиной, номер которой подаётся ей на вход, и допустить свой вход эта проверяющая МТ не сможет, даже если он является номером какой-то МТ, останавливающейся на пустом входе. В случае пустого слова у ДМТ также могут возникнуть трудности, это произойдёт если поданный ей на вход номер окажется номером НМТ с бесконечными вычислениями, тогда ДМТ при моделировании работы НМТ на пустом слове может пойти по бесконечной ветви дерева вычислений НМТ. Но вот НМТ, она же вроде прекращает вычисления при достижении допускающего состояния, и при моделировании работы другой НМТ на пустом слове (которая останавливается на пустом слове, т.е. имеет конечное допускающее вычисление, но некоторые вычисления на пустом слове при этом могут быть бесконечными), даже если у этой НМТ (вычисления которой моделируются) есть бесконечные ветви, моделирующая НМТ, одновременно исследуя все ветви вычислений той машины, дойдёт до её допускающей конфигурации и прервёт свои вычисления, приняв вход (при условии что НМТ, номер которой подан на вход, останавливается на пустом слове). Странно получается...

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

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

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

iifat в сообщении #1321946 писал(а):

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

Хотел сказать вот ещё что по этому поводу. Мы же не можем просто говорить "Пусть $M$ -- НМТ, решающая проблему выполнимости булевых формул...", по-хорошему мы должны предъявить алгоритм, следуя которому (являясь которым) машина $M$ будет а) всегда выдавать правильное решение; б) делать это в течение конечного числа шагов. Поэтому, на мой взгляд, естественно задаваться вопросом, как именно должен работать этот недетерминированный алгоритм. А двухэтапная процедура с угадыванием доказательства $x \in L$ и последующей проверкой корректности этого доказательства -- по видимому, самый простой и очевидный способ построения недетерминированных алгоритмов для переборных задач вроде проверки выполнимости булевых формул. По моим представлениям, другие недетерминированные алгоритмы, во-первых, потребуют применения более сложных алгоритмических идей, а во-вторых, не дадут ничего нового для иллюстрации "вычислительной мощи" НМТ по сравнению с ДМТ. Видимо, именно поэтому во многих изложениях при пояснении работы НМТ говорят о ней как о машине, которая при решении задач сначала делает недетерминированное предположение, а затем детерминированно проверяет правильность этого предположения.

Цитата:

Ссылочку можно? Для автоматов с магазинной памятью это не так, точно помню, а реализовать такой автомат на МТ, как понимаю, можно.

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

[iifat]

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

Мы же не можем просто говорить "Пусть М -- НМТ, решающая проблему выполнимости булевых формул...", по-хорошему мы должны предъявить алгоритм

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

[SteelRend]

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

-- 23.06.2018, 14:26 --

Xaositect в сообщении #1321952 писал(а):

Недетерминированная машина, которая распознает язык, должна иметь 2 терминальных состояния - YES и NO. И для того, чтобы распознавать язык $L$, любой вычислительный путь на любом слове должен быть конечным.

Любой ли? А что, если у НМТ в дереве вычислений над словом, которое она допускает, существуют также бесконечные ветви (вычисления)? Т.е. у неё есть как конечные допускающие вычисления, как конечные отклоняющие, так и бесконечные (т.е. не допускающие).