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

[ShMaxG]

Возникли вопросы по языкам:

1. Множество разрешимых языков счетно? (а перечислимо? разрешимо?)
2. Множество перечислимых языков счетно? (а перечислимо? разрешимо?)

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

Подскажите пожалуйста в каком направлении думать.

[TypucT]

Счетно и то и другое. Достаточно языку поставить в соответсвие натуральное число, двоичной записью которого будет описание соответствующей МТ.

[Xaositect]

Насчет счетности уже ответили.
Насчет разрешимости - любая МТ перечисляет некоторое множество, а вот множество машин, которые разрешают множества, неперечислимо($\Pi_2$ в арифметической иерархии, если не ошибаюсь)

[ShMaxG]

Интересно, на самом деле, счетно, но не перечислимо. Т.е. занумеровать множество можно, а перечисляющей МТ нет...

Вот еще задачка:

$$ L_{stop} = \left\{ {M\left| {{\text{ МТ с описанием < M > останавливается на пустой ленте}}} \right.} \right\} $$

m-полон во множестве перечислимых языков.

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

$$ L_{stop} $$

, т.е. имеет место m-сводимость.

[Xaositect]

m-полнота означает, что если мы можем решить задачу $L_{stop}$, то с помощью нее сможем решить любую перечислимую задачу, а не наоборот.
Идея примерно такая:
Пусть $L$ - некоторое перечислимое множество, $M$ останавливается на слове, если оно лежит в $L$ и не останавливается иначе.
Тогда остаточный язык $L_a = \{x|ax\in L\}$ тоже перечислим, пусть машина $M_a$ останавливается на словах из $L_a$ и не останавливается на тех, что не входит. Мы можем получить программу $M_a$ из программы $M$ рекурсивно.
Тогда $a\in L \Leftrightarrow M_a\in L_{stop}$

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

Xaositect писал(а):

Насчет разрешимости - любая МТ перечисляет некоторое множество, а вот множество машин, которые разрешают множества, неперечислимо($\Pi_2$ в арифметической иерархии, если не ошибаюсь)

Угу, точно так. $\Pi^0_2$, причём полное (то есть вычислимо изоморфное дополнению ко второму скачку вычислимого множества).

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

Xaositect писал(а):

m-полнота означает, что если мы можем решить задачу $L_{stop}$, то с помощью нее сможем решить любую перечислимую задачу, а не наоборот.

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

Вообще, странно как-то обсуждать теорию рекурсивных функций в такой чересчур общей терминологии. Так и хочется спросить автора темы: откуда Вы берёте такие определения? Такие словосочетания, как "теорема Райса", "s-m-n теорема", "теорема о неподвижной точке" Вам что-нибудь говорят?

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

ShMaxG писал(а):

Подадим на вход этим МТ пустой вход. Если остановилась, то эта МТ входит в

$$ L_{stop} $$

, т.е. имеет место m-сводимость.

Сами то поняли, что написали (красное выделение моё)? Причём это не опечатка, заметьте

[TypucT]

Т.к.

Xaositect писал(а):

любая МТ перечисляет некоторое множество

то множество перечислимых языков перечислимо и разрешимо в смысле ShMaxG.

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

TypucT писал(а):

Т.к.

Xaositect писал(а):

любая МТ перечисляет некоторое множество

то множество перечислимых языков перечислимо и разрешимо в смысле ShMaxG.

А мне вот нифига не ясно. Призываю ShMaxG пояснить, что значит "машина перечисляет язык". Означает ли это, что на ленте выписываются друг за другом все слова этого языка, отделённые друг от друга каким-нибудь особым образом (например, пустой ячейкой)? Или это означает что-то другое?

[TypucT]

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

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

ShMaxG писал(а):

Возникли вопросы по языкам:

1. Множество разрешимых языков счетно? (а перечислимо? разрешимо?)
2. Множество перечислимых языков счетно? (а перечислимо? разрешимо?)

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

Подскажите пожалуйста в каком направлении думать.

На первый вопрос ответ таков: счётно, не перечислимо, не разрешимо. Выше достаточно хорошо об этом сказано.

На второй вопрос... Со счётностью всё ясно. А для ответа на остальное требуется прежде всего чёткое определение того, что значит "машина перечисляет язык". Ответы зависят от этого определения!!!

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

TypucT писал(а):

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

Вы гадаете или у Вас точная информация от самого ShMaxG, которую он Вам на ушко сказал?

[ShMaxG]

Значит так. По порядку.

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

Так и хочется спросить автора темы: откуда Вы берёте такие определения? Такие словосочетания, как "теорема Райса", "s-m-n теорема", "теорема о неподвижной точке" Вам что-нибудь говорят?

Нет, не проходили.

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

Сами то поняли, что написали (красное выделение моё)? Причём это не опечатка, заметьте

Да, это я зря так

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

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

[TypucT]

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

Вы гадаете или у Вас точная информация от самого ShMaxG, которую он Вам на ушко сказал?

Думаю, есть третий вариант

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

Мое бездоказательное утверждение не намного хуже этих:

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

Xaositect писал(а):

множество машин, которые разрешают множества, неперечислимо($\Pi_2$ в арифметической иерархии, если не ошибаюсь)

Угу, точно так. $\Pi^0_2$, причём полное (то есть вычислимо изоморфное дополнению ко второму скачку вычислимого множества).

Не понимаю, как эти аргументы убедили ShMaxG.

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

ShMaxG писал(а):

Нам дали такие определения...

Ну, тады ладно. Такие --- значит такие.

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

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

[Xaositect]

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

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

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

[TypucT]

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

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

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

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

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

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