Cтраница 3
Семейство 5 рекурсивно перечислимых множеств наз. [31]
Существуют два непересекающихся перечислимых множества X и Y, которые не отделяются никаким разрешимым множеством. [32]
Рекурсивными и рекурсивно перечислимыми множествами являются подмножества множества N, соответствующие разрешимым и частично разрешимым предикатам. Рекурсивные множества будут вкратце рассмотрены в § 1, а затем большая часть этой главы будет посвящена изучению рекурсивно перечислимых множеств. [33]
Теорема 7.4. Всякое рекурсивно перечислимое множество является К-множеством. Существует К-множество, которое не является рекурсивно перечислимым. [34]
Список - это рекурсивно перечислимое множество. [35]
ПЕРЕЧИСЛЙМОЕ МНОЖЕСТВО, рекурсивно перечислимое множество, - множество, для к-рого существует алгоритм, последовательно шаг за шагом выдающий в качестве результата элементы этого множества. [36]
Установим, что всякое перечислимое множество примитивно перечислимо. [37]
Оказывается, существуют рекурсивно перечислимые множества которые не рекурсивны. К числу таких множеств относится аксиоматическая система обычной арифметики. Известно, что множество теорем будет хотя и рекурсивно перечислимо, но не рекурсивно. [38]
Докажите, что существует перечислимое множество, для которого прямой пересчет ( последовательность элементов в порядке возрастания без повторений) его дополнения не ограничен сверху никакой всюду определенной вычислимой функцией. Докажите, что это множество является простым. [39]
Существуют несравнимые по Тьюрингу перечислимые множества. [40]
Покажите, что всякое бесконечное перечислимое множество содержит бесконечное разрешимое подмножество. [41]
Нам нужно, чтобы перечислимое множество S имело иммунное дополнение. [42]
ПРОСТОЕ МНОЖЕСТВО - рекурсивно перечислимое множество натуральных чисел, дополнение к-рого есть иммунное множество. Рекурсивная теория множеств) между разрешимыми множествами и творческими ( креативными) множествами - последние являются наибрлыпими среди перечислимых множеств в смысле т - сводимости. [43]
Доказать, что рекурсивно перечислимых множеств счетное число. [44]
Дадим теперь характеризацию рекурсивно перечислимых множеств с помощью рекурсивных функций. [45]