перечислимые мн-ва (Верещагин, Шень, ч. 3. Задачи 11, 12)

[alleut]

Цитата:

11. Покажите, что всякое бесконечное перечислимое множество можно записать в виде ${a(0); a(1); a(2); ...}$, где $a$ - вычислимая функция, все значения которой различны. (Указание: в ходе перечисления удаляем повторения.)

Сначала перечислим множество без повторений. Получится перечислимое множество, которое является областью значений некой вычислимой функции. Так?

Цитата:

12. Покажите, что всякое бесконечное перечислимое множество содержит бесконечное разрешимое подмножество. (Указание: воспользуемся предыдущей задачей и выберем возрастающую подпоследовательность.)

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

[Xaositect]

alleut в сообщении #620581 писал(а):

Сначала перечислим множество без повторений. Получится перечислимое множество, которое является областью значений некой вычислимой функции. Так?

Я в этой фразе не вижу смысла. Как вы определяете функцию $a$?

[alleut]

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

alleut в сообщении #620581 писал(а):

Сначала перечислим множество без повторений. Получится перечислимое множество, которое является областью значений некой вычислимой функции. Так?

Я в этой фразе не вижу смысла. Как вы определяете функцию $a$?

И в самом деле, бессмысленно

Ну, может быть, аналогично рассуждению из книги: $X$ перечислимое множество, являющееся областью определения некоторой вычислимой алгоритмом $A$ функции $f$. Тогда $X$ будет областью значения функции $a(x)$:

$a(x) = x$, если $A$ заканчивает работу на $X$ и если $x$ еще не было;
в других случаях $a(x)$ не определена

[Xaositect]

Нет, так не пойдет. В задаче требуется, чтобы все $a(n)$ были определены.
Попробуйте отталкиваться от исходного определения перечислимого множества, через перечисляющую машину.

[alleut]

Цитата:

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

Цитата:

Функция f с натуральными аргументами и значениями называется вычислимой, если существует алгоритм, её вычисляющий.

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

[Xaositect]

alleut в сообщении #620651 писал(а):

Цитата:

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

Цитата:

Функция f с натуральными аргументами и значениями называется вычислимой, если существует алгоритм, её вычисляющий.

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

Да, это правильная идея.
Осталось только сделать так, чтобы $a(n)$ были различны.

[alleut]

Цитата:

сталось только сделать так, чтобы были различны.

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

А во второй задаче, быть может, можно как-то использовать теорему Поста?

[Xaositect]

alleut в сообщении #620711 писал(а):

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

Верно.

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

Зачем же нам это предлагают? А затем, что если у нас есть последовательность или, что то же самое, перечисление, то мы можем сидеть, смотреть на выдаваемые числа, и если некоторое число, которое у нас есть, входит в нашу последовательность, то мы об этом рано или поздно узнаем. А для того, чтобы у нас множество было разрешимым, у нас должен быть способ не только узнать, что число входит в последовательность, а еще узнать, что оно в нее точно не входит.

А теперь подумайте, как нам помогает в этом возрастание нашей последовательности и попробуйте сами изложить доказательство того, что возрастающая вычислимая последовательность $a(0), a(1), \dots$ перечисляет разрешимое множество.

[alleut]

Цитата:

Нам предлагают взять и выделить из множества вычислимую возрастающую последовательность. Я думаю, Вы теперь уже можете объяснить, как это сделать.

Возьмём, например, первый элемент, потом пойдём по $n$ в последовательности $a(n)$, выбирая те элементы, которые больше предыдущего?

Цитата:

А теперь подумайте, как нам помогает в этом возрастание нашей последовательности

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

[Xaositect]

Все верно.

[alleut]

Xaositect, большое спасибо за помощь. Теперь я, похоже, немного ближе к началу понимания