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

[Xaositect]

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

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

Если говорим о распознавании языков, то такого быть не должно.
Но такую ситуацию всегда можно исправить.

[mihaild]

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

Давайте правильно употреблять термины.

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

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

Пустой вход -- имеется в виду пустой язык $L_{\emptyset} = \emptyset$ или пустое слово $\lambda$?

Пустое слово.

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

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

Во-первых, считаем, что передаем номер детерменированной машины.
Во-вторых, можно обходить все ветви параллельно.

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

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

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

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

по-хорошему мы должны предъявить алгоритм, следуя которому (являясь которым) машина $M$ будет а) всегда выдавать правильное решение; б) делать это в течение конечного числа шагов

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

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

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

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

-- 23.06.2018, 13:49 --

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

Но такую ситуацию всегда можно исправить.

Рассмотрим НМТ, которая из начального состояния либо сразу переходит отвергающее, либо запускает полученную на вход МТ и переходит в принимающее состояние, когда та остановится. Как тут исправить?

[SteelRend]

Ещё кое-что добавлю. В той же книге Громковича (а других источников на эту тему я не читал), говорится о классе так называемых рекурсивно перечислимых языков $\mathcal{L}_{RE}$. Если $L \in \mathcal{L}_{RE}$, то существует МТ $M$, распознающая язык $L$, т.е. допускающая каждое слово $x \in L$, но для слов $y \in (\Sigma^\star - L)$ эта машина может иметь бесконечные вычисления. Например, язык проблемы останова $L_H = \{Kod(M)\#x | x \in \{0, 1\}^{\star}$ и $M$ останавливается на $x \}$ как раз относится к рекурсивно перечислимым языкам -- всякая МТ $A$, допускающая этот язык, может определить останов для машин Тьюринга, которые всегда останавливаются (т.е. допустить свой вход), но для тех машин, которые работают бесконечно, МТ $A$ также будет работать бесконечно, т.е. не сможет определить останов другой машины. Есть МТ, которые всегда останавливаются на любом входе (вообще на любом), и о языках, которые они допускают, говорят, что они являются рекурсивными языками из класса $\mathcal{L}_{R}$. И Тезис Чёрча-Тьюринга (который устанавливает формальное определение алгоритма) там записан так:

Цитата:

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

[Xaositect]

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

Рассмотрим НМТ, которая из начального состояния либо сразу переходит отвергающее, либо запускает полученную на вход МТ и переходит в принимающее состояние, когда та остановится. Как тут исправить?

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

[SteelRend]

В общем, я понял. НМТ $M$ допускает/принимает/распознаёт слово $w$, если существует конечное допускающее вычисление машины $M$ над входом $w$ (НМТ $M$ допускает язык $L$, если она допускает каждое слово $x \in L$). Теперь рассмотрим язык "множество номеров всех машин Тьюринга, останавливающихся на пустом слове $\lambda$". Что в точности значит утверждение "Машина Тьюринга $M$ останавливается на пустом слове $\lambda$", если машина $M$ -- недетерминированная? Два варианта: а) НМТ $M$ останавливается на $\lambda$, если существует конечное вычисление над $\lambda$ (не обязательно допускающее!) б) НМТ $M$ останавливается на $\lambda$, если все её вычисления над этим входом конечны. Теперь рассмотрим вопрос, может ли детерминированная МТ $A$ допускать этот язык. Предположим, что ей попался номер НМТ $M$, останавливающейся на пустом слове. Если принять определение а), то эта НМТ $M$ может иметь бесконечные вычисления. В этом случае наша моделирующая ДМТ $A$ может пойти по бесконечной ветви в дереве вычислений $M$ и никогда не завершить работу (хотя я в точности не помню алгоритм поиска в ширину в дереве, который и должна выполнять ДМТ, моделирующая НМТ). Пусть теперь $A$ недетерминированная. Тогда, поскольку $M$ останавливается на пустом слове, она имеет вычисления конечной длины над ним (не обязательно допускающие). Когда $A$ дойдёт до допускающей или отклоняющей конфигурации $M$, она прекратит работу и примет вход, т.е. в отличие от детерминированной МТ она всегда будет останавливаться, и поэтому действительно будет принимать этот язык. Если принять определение б), то обе машины (детерминированная и недетерминированная) смогут распознать этот язык. Но при этом мы видим, что недетерминированные машины в самом деле могут распознавать языки, которые не могут распознавать детерминированные, а равенство классов распознаваемых языков выполняется только в случае, если НМТ не имеет бесконечных вычислений (видимо, это и есть то ограничение, о котором говорил mihaild), т.е. именно как модель алгоритма (всегда останавливающаяся) ДМТ столь же мощна, как и НМТ, но не каждая МТ является алгоритмом (тезис Чёрча-Тьюринга).