|
Помогите, пожалуйста, доказать, что если из бесконечного вычислимо перечислимого множества натуральных чисел удалить вычислимое множество элементов, то останется вычислимо перечислимое множество. задан 26 Июн '17 19:54 
12345Ann |
|
Пусть имеется алгоритмическая процедура, перечисляющая все элементы множества A. Для каждого элемента n, который предполагается напечатать, проверяем при помощи алгоритма, принадлежит ли он рекурсивному (вычислимому) множеству B. Если окажется, что не принадлежит, то печатаем его. Если принадлежит, то не печатаем, и продолжаем работать дальше. Описанная процедура печатает в точности все элементы теоретико-множественной разности A-B. отвечен 26 Июн '17 20:23 
falcao А здесь важно то, что раньше вычислимо перечислимое множество было бесконечным, но в конце об этом не говориться?
(26 Июн '17 20:38)
12345Ann
А если удалять всё четные числа, получается тоже самое? Ведь все четные числа - это вычислимое множество?
(26 Июн '17 20:48)
12345Ann
@12345Ann: конечно или бесконечно -- это никак не влияет. Если множество конечно, то оно заведомо перечислимо, то есть это как бы не очень интересный случай. Множество чётных чисел вычислимо. Его рассмотрение здесь возможно как один из частных случаев.
(26 Июн '17 21:10)
falcao
|