2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.

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

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

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

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему На страницу Пред.  1, 2
 
 Re: Счётное неперечислимое множество
Сообщение04.08.2009, 10:57 


04/08/09
16
Dialectic в сообщении #230439 писал(а):
Существуют ли такие? Вроде "да". Ведь перечисляющий алгоритмов счётно, а счётных множеств не менее континуума. Поэтому существует хотя бы одно счётное множество, для которого не имеется алгоритма его перечисляющего. Я верно рассуждал?

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

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

 Профиль  
                  
 
 Re: Счётное неперечислимое множество
Сообщение04.08.2009, 17:05 


27/08/06
579
hexamino в сообщении #232783 писал(а):
Верно. И даже можно привести простые примеры таких множеств. Можете посмотреть в книге Верещагина и Шеня "Вычислимые функции" (она бесплатно доступна в электронном виде).

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

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

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

 Профиль  
                  
 
 Re: Счётное неперечислимое множество
Сообщение24.08.2010, 13:34 


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

 Профиль  
                  
 
 Re: Счётное неперечислимое множество
Сообщение24.08.2010, 15:10 


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 19 ]  На страницу Пред.  1, 2

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group