Вопросы по теории языков и МТ

[Профессор Снэйп]

Xaositect писал(а):

Профессор Снэйп в сообщении #196766 писал(а):

Не совсем так. Это $T$-полнота. А $m$-полнота --- это когда фраза "с помощью неё" понимается в очень специальном узком смысле.

Ну, у меня обращение к оракулу идет один раз в конце алгоритма сведения, вроде это $m$-сводимость. Точного определения не помню, а литературы под рукой не было.

Не-а! Когда один раз обращаются к оракулу в конце алгоритма --- это $tt$-сводимость (даже $btt$-сводимость). А $m$-сводимость --- это когда к оракулу обращаются один раз в конце алгоритма и при этом положительный ответ оракула равносилен положительному ответу на исходный вопрос.

Пусть, например, $K$ --- множество проблемы остановки и $\overline{K}$ --- его дополнение. Ясно, что $\overline{K} \leqslant_{btt} K$: можно для каждого $x$ сразу спросить ''$x \in K$?'' и на вопрос ''$x \in \overline{K}$?'' дать протвоположный ответ. Однако $\overline{K} \not\leqslant_m K$, и это легко доказывается

Но доказательство $m$-сводимости перечислимого языка к $L_{stop}$ Вы дали совершенно корректное, я не спорю с этим. Просто уточняю, что же такое эта самая сводимость

Добавлено спустя 11 минут 37 секунд:

TypucT писал(а):

Возможно я ошибся. Я не смог доказать, что по описанию МТ, которая всегда останавливается, можно доказать, что она всегда останавливается.

Само собой не смогли!!! Останавливаемость МТ при любом входе --- это полное $\Pi^0_2$-свойство, а доказуемость --- $\Sigma^0_1$-свойство. А поскольку полное $\Pi^0_2$-множество не лежит в $\Sigma^0_1$, то и доказательства, которое Вы искали, просто не существует

TypucT писал(а):

Профессор Снэйп писал(а):

Что касается описаний МТ, разрешающих языки, то их множество не будет перечислимым. Следовательно, разрешимым оно также не будет. Как это доказать, не ссылаясь на теорему Райса или теорему о неподвижной точке?.. Хороший вопрос! Хотелось бы знать, на что вообще можно ссылаться

Вы уже сослались Хочется увидеть хоть какое-то доказательство.

Теорема Райса утверждает неразрешимость (но не неперечислимость) всякого нетривиального свойства перечислимых языков. Отсюда свойство языка "быть разрешимым" неразрешимо. Это дает нам половину ответа - множество разрешимых языков неразрешимо.

Как быть с перечислимостью?

Есть расширенный вариант теоремы Райса, характеризующий перечислимые индексные множества. У меня сейчас Роджерса под рукой нет, но что-то вроде следующего:

Для класса частично рекурсивных функций $\mathcal{F}$ индексное множество этого класса перечислимо тогда и только тогда, когда существует перечислимый класс конечных функций $\mathcal{G}$, такой что $\mathcal{F} = \{ f : (\exists g \in \mathcal{G})(g \subseteq f) \}$.

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

Пока что, судя по заданным вопросам, ясно лишь, что у них какой-то странный курс, где всё на пальцах и нет никакого формализма. Вот $m$-сводимость есть, и это хорошо... Но я не понимаю, как можно работать с $m$-сводимостью без $s-m-n$-теоремы. Я у него спросил, знает ли он такую теорему. Он ответил, что нет. Я в затруднении

Можно попробовать зайти с такого боку.

1) Множество разрешимо тогда и только тогда, когда оно само и его дополнение перечислимы. Это простое утверждение называется теоремой Поста.

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

3) Все множества, $m$-сводимые к перечислимому множеству, также перечислимы. Это довольно простое утверждение, которое легко доказывается.

4) Приняв во внимание все предыдущие пункты, показываем, что дополнение к проблеме остановки $m$-сводится к множеству описаний МТ, разрешающих какой-то язык. После чего бурно радуемся, ибо всё, что надо, уже доказано

ShMaxG, Вас устроит такое доказательство? Если схема понятна, но не ясны какие-то детали, то спрашивайте по пунктам

[ShMaxG]

Профессор Снэйп писал(а):

Как это доказать, не ссылаясь на теорему Райса или теорему о неподвижной точке?.. Хороший вопрос! Хотелось бы знать, на что вообще можно ссылаться

А, даже так. Я уже взял в библиотеке книжку Верещагина, почитаю об этом. Вообще, эти вопросы придумало не начальство, а я. (Только задача о m-полноте от начальства).

Вечером поразбираюсь в пунктах

[TypucT]

Профессор Снэйп писал(а):

TypucT писал(а):

Возможно я ошибся. Я не смог доказать, что по описанию МТ, которая всегда останавливается, можно доказать, что она всегда останавливается.

Само собой не смогли!!! Останавливаемость МТ при любом входе --- это полное $\Pi^0_2$-свойство, а доказуемость --- $\Sigma^0_1$-свойство. А поскольку полное $\Pi^0_2$-множество не лежит в $\Sigma^0_1$, то и доказательства, которое Вы искали, просто не существует

Тут я пас. Постараюсь проверить, Роджерс мне в помощь (терминология же оттуда?).

[Профессор Снэйп]

TypucT писал(а):

...Роджерс мне в помощь (терминология же оттуда?).

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

Роджерс --- очень хороший учебник. Если он у Вас есть --- читайте. ShMaxG'у я бы тоже посоветовал читать его вместо Верещагина. Особенно учитывая тот факт, что начальство даёт ему задачи про $m$-полноту!

P. S. Кстати, я там был немного неправ. Утверждение, известное как теорема Райса, действительно относится только к вычислимым индексным множествам. А то утверждение, которое я привёл, известно как теорема Райса-Шапиро. Два автора вместо одного

[ShMaxG]

Профессор Снэйп писал(а):

дополнение к проблеме остановки $m$-сводится к множеству описаний МТ, разрешающих какой-то язык.

Вот это не очень понятно...

[Профессор Снэйп]

ShMaxG писал(а):

Профессор Снэйп писал(а):

дополнение к проблеме остановки $m$-сводится к множеству описаний МТ, разрешающих какой-то язык.

Вот это не очень понятно...

Ну, это как раз просто.

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

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

Описание построенной нами МТ находится по описанию исходной МТ эффективно, то есть при помощи некоторого алгоритма. Этот самый алгоритм как раз и осуществляет $m$-сводимость описаний МТ, не останавливающихся на пустом входе, к описаниям МТ, разрешающим языки.

[ShMaxG]

Спасибо, стало понятно

А что значит в решении задачи Xaositect "остаточный язык" и

Xaositect писал(а):

Мы можем получить программу $M_a$ из программы $M$ рекурсивно.

Рекурсивно это как?

Добавлено спустя 8 минут 36 секунд:

Профессор Снэйп писал(а):

ShMaxG'у я бы тоже посоветовал читать его вместо Верещагина. Особенно учитывая тот факт, что начальство даёт ему задачи про $m$-полноту!

Хорошо, я просто вначале подумал начать с чего-нибудь не слишком сложного.

Добавлено спустя 1 минуту 26 секунд:

Да, и еще - в каком порядке лучше всего читать главы из Роджерса?

[Профессор Снэйп]

ShMaxG писал(а):

Спасибо, стало понятно

А что значит в решении задачи Xaositect "остаточный язык" и

Xaositect писал(а):

Мы можем получить программу $M_a$ из программы $M$ рекурсивно.

Рекурсивно это как?

Ну, насколько я его понял, для произвольных слова $a$ и языка $L$ "остаточный язык" $L_a$ --- это язык, состоящий из всех таких слов $x$, что конкатенация $ax$ принадлежит $L$. То есть

$$ L_a = \{ x \in \Sigma^\ast : ax \in L \}. $$

Он пользуется тем, что пустое слово принадлежит $L_a$ тогда и только тогда, когда $a \in L$.

А "рекурсивно" в данном случае означает то же самое, что и эффективно. То есть алгоритмически, посредством некоторого алгоритма.

Добавлено спустя 8 минут 17 секунд:

ShMaxG писал(а):

Да, и еще - в каком порядке лучше всего читать главы из Роджерса?

Если с нуля, то подряд И желательно с прорешиванием всех упражнений, в них довольно много спрятано.

[ShMaxG]

Следующая задача такая:

Показать, что язык

$$ L_{empty} = \left\{ {M\left| {L\left( M \right) = \emptyset } \right.} \right\} $$

m-полон в

$$ \Pi _1 $$

.

Пока думаю...

Добавлено спустя 13 минут 7 секунд:

Произвольный вход подаем на МТ, перечисляющую некоторый язык из дополнения

$$ \Pi _1 $$

. По этой МТ мы строим МТ2, которая делает следующее. Она вычисляет длину входа, и затем делает столько тактов, какова длина этого слова. Если исходная МТ остановилась, то МТ2 печатает символ. Если нет, ничего не печатает.

Т.е. пытался применить Вашу схему.

[Xaositect]

А у нас МТ не обязательно останавливается после количества тактов, равного длине слова.
Время работы может быть и $2^n$, и $2^{2^n}$ и гораздо более страшным, типа функции Аккермана.

Добавлено спустя 1 минуту 30 секунд:

Но идея правильная, надо запустить машину, перечисляющую дополнение, на заданном входе.

[ShMaxG]

А, я понял, в чем фишка там и здесь.

[Профессор Снэйп]

ShMaxG писал(а):

Следующая задача такая:

Показать, что язык

$$ L_{empty} = \left\{ {M\left| {L\left( M \right) = \emptyset } \right.} \right\} $$

m-полон в

$$ \Pi _1 $$

.

Пока думаю...

Добавлено спустя 13 минут 7 секунд:

Произвольный вход подаем на МТ, перечисляющую некоторый язык из дополнения

$$ \Pi _1 $$

. По этой МТ мы строим МТ2, которая делает следующее. Она вычисляет длину входа, и затем делает столько тактов, какова длина этого слова. Если исходная МТ остановилась, то МТ2 печатает символ. Если нет, ничего не печатает.

Т.е. пытался применить Вашу схему.

ShMaxG писал(а):

А, я понял, в чем фишка там и здесь.

Ну, если поняли, то, наверное, уже и не надо ничего пояснять. Но на всякий случай прокомментирую.

Здесь идея даже проще. Пусть есть перечислимый язык и он равен $L(M)$ для некоторой машины $M$. Строим по каждому слову $a$ машину $M_a$ следующим образом. Эта машина должна, получив на вход любое слово, запустить машину $M$ со входом $a$ и ждать, пока та закончит вычисления в состоянии "Да". Если это в некоторый момент происходит, то она тут же останавливается и даёт ответ "Да", в противном случае продолжает вычисления. Зависимость $a \mapsto M_a$ эффективна и определяет нужную нам $m$-сводимость.

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

Добавлено спустя 3 минуты 4 секунды:

Xaositect писал(а):

Время работы может быть и $2^n$, и $2^{2^n}$ и гораздо более страшным, типа функции Аккермана.

И даже ещё более страшным, чем функция Аккремана!

[Профессор Снэйп]

TypucT писал(а):

Профессор Снэйп писал(а):

TypucT писал(а):

Возможно я ошибся. Я не смог доказать, что по описанию МТ, которая всегда останавливается, можно доказать, что она всегда останавливается.

Само собой не смогли!!! Останавливаемость МТ при любом входе --- это полное $\Pi^0_2$-свойство, а доказуемость --- $\Sigma^0_1$-свойство. А поскольку полное $\Pi^0_2$-множество не лежит в $\Sigma^0_1$, то и доказательства, которое Вы искали, просто не существует

Тут я пас. Постараюсь проверить, Роджерс мне в помощь (терминология же оттуда?).

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

Достаточно заметить, что множество доказуемых утверждений всегда перечислимо. Ведь что такое доказательство? С формальной точки зрения это просто последовательность символов, подчиняющихся определённым правилам, причём правила эти заданы эффективно. Другими словами, для каждой разумной формальной логической системы (типа исчисления предикатов, арифметики Пеано и т. п.) существует алгоритм, который по каждой последовательности символов за конечное время проверяет, является ли она формальным доказательством в этой системе. Ну а раз так, то можно просто перебирать все конечные последовательности символов и для каждой из них проверять, является ли она доказательством. По ходу перебора мы будем (эффективно, то есть алгоритмически) получать список всех доказательств. Ну и, естественно, список всех доказуемых утверждений, ибо из каждого доказательства можно выделить утверждение, которое оно, собственно, доказывает.

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

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

Какой отсюда вывод? Множество МТ, всегда останавливаемость которых доказуема, перечислимо. Если бы оно совпадало с множеством всех МТ, которые всегда останавливаются, то последнее также было бы перечислимым. Однако по ходу дискуссии в этой теме мы уже много раз заметили, что это не так!

[ShMaxG]

Перечислимо ли множество всех МТ, головка которых не может двигаться влево? (Пока нет идей...)

[Профессор Снэйп]

ShMaxG писал(а):

Перечислимо ли множество всех МТ, головка которых не может двигаться влево? (Пока нет идей...)

Смотря что Вы понимаете под словом "не может".

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