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

задан 31 Май 16:36

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

(31 Май 16:56) falcao

А пример перечислимого множества верный?

(31 Май 18:06) Drag0n

@Drag0n: все разрешимые множества перечислимы -- в частности, пример множества чётных чисел годится. Но надо понимать, что такие множества -- не редкость, и лучше приводить более содержательные примеры, беря их среди не разрешимых множеств.

(31 Май 18:26) falcao

А разве проблема остановки Машины Тьюринга неперечислима? Она ведь не разрешима,но перечислима

(1 Июн 9:27) Drag0n

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

Из примера неразрешимого, но перечислимого множества легко строится и пример неперечислимого за счёт перехода к дополнению.

(1 Июн 11:19) falcao
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×1,541

задан
31 Май 16:36

показан
79 раз

обновлен
1 Июн 11:19

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru