Помогите, пожалуйста, доказать, что если из бесконечного вычислимо перечислимого множества натуральных чисел удалить вычислимое множество элементов, то останется вычислимо перечислимое множество.

задан 26 Июн '17 19:54

10|600 символов нужно символов осталось
1

Пусть имеется алгоритмическая процедура, перечисляющая все элементы множества A. Для каждого элемента n, который предполагается напечатать, проверяем при помощи алгоритма, принадлежит ли он рекурсивному (вычислимому) множеству B. Если окажется, что не принадлежит, то печатаем его. Если принадлежит, то не печатаем, и продолжаем работать дальше. Описанная процедура печатает в точности все элементы теоретико-множественной разности A-B.

ссылка

отвечен 26 Июн '17 20:23

А здесь важно то, что раньше вычислимо перечислимое множество было бесконечным, но в конце об этом не говориться?

(26 Июн '17 20:38) 12345Ann

А если удалять всё четные числа, получается тоже самое? Ведь все четные числа - это вычислимое множество?

(26 Июн '17 20:48) 12345Ann

@12345Ann: конечно или бесконечно -- это никак не влияет. Если множество конечно, то оно заведомо перечислимо, то есть это как бы не очень интересный случай.

Множество чётных чисел вычислимо. Его рассмотрение здесь возможно как один из частных случаев.

(26 Июн '17 21:10) falcao

@falcao: Большое спасибо! Все поняла.

(26 Июн '17 21:21) 12345Ann
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×829
×142

задан
26 Июн '17 19:54

показан
403 раза

обновлен
26 Июн '17 21:21

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

по почте:

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

по RSS:

Ответы

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

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