Счётное неперечислимое множество

[hexamino]

Dialectic в сообщении #230439 писал(а):

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

Верно. И даже можно привести простые примеры таких множеств. Можете посмотреть в книге Верещагина и Шеня "Вычислимые функции" (она бесплатно доступна в электронном виде).

Можете попробовать построить такой пример самостоятельно. Подсказка: проблема останова.

[Dialectic]

hexamino в сообщении #232783 писал(а):

Верно. И даже можно привести простые примеры таких множеств. Можете посмотреть в книге Верещагина и Шеня "Вычислимые функции" (она бесплатно доступна в электронном виде).

Благодарю. Посмотрю если книгу найду. Мне интересен такой пример.

hexamino в сообщении #232783 писал(а):

Можете попробовать построить такой пример самостоятельно. Подсказка: проблема останова.

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

[Kenny2]

hexamino, про подсказку "проблема останова" не путаете ли с неразрешимым множеством?
И все же вопрос остался открытым, на какой странице, какого учебника лежит пример счётного неперечислимого множества?
Кстати, а любое несчетное множество - неперечислимо? правильно я понимаю??

[Kenny2]

Но я кажется уже сам допетрил: множество номеров самоприменимых машин Тьюринга является неразрешимым перечислимым множеством. Следовательно, по теореме Поста, дополнение к нему и есть искомое "счетное неперечислимое множество". Правильно?