Cтраница 1
Перечислимые множества д иоф а нтовы, следовательно, эти два класса совпадают. [1]
Перечислимое множество является т-пол-ным тогда и только тогда, когда его дополнение эффективно неперечислимо. [2]
Рекурсивно перечислимое множество А называется т-униеер-салъным, если к нему m - сводится любое рекурсивно перечислимое множество. [3]
Рекурсивно перечислимое множество Е слов в данном алфавите рекурсивно, или разрешимо, если его дополнение Е рекурсивно перечислимо. Из предыдущего следует, что не всякое рекурсивно перечислимое множество разрешимо. [4]
Существуют перечислимые множества, не являющиеся разрешимыми. [5]
Существуют перечислимые множества с эффективно неперечислимыми дополнениями. [6]
Всякое га-полное перечислимое множество имеет эффективно неперечислимое дополнение. [7]
Существует перечислимое множество пар натуральных чисел, универсальное для класса всех перечислимых множеств натуральных чисел. [8]
Рассмотрим универсальное перечислимое множество Z четверок вида ( п, х, y t), где п, х и у - числа, a t - образец. Говоря об универсальности, мы имеем в виду, что при различных п среди сечений Zn содержатся все перечислимые множества троек. [9]
Диофантовость перечислимых множеств, Докл. [10]
Если рекурсивно перечислимое множество А есть совокупность значений функции К ( п х) для некоторого п, то число п назовем постовским номером множества А и обозначим А пп пп. У - семейство всех рекурсивно перечислимых множеств, называется постовской нумерацией семейства ЗР. [11]
Если рекурсивно перечислимое множество непусто, то оно содержит нек-рый элемент. Пусть А - алгоритмически проверяемое свойство натуральных чисел. Тогда, если опровергнуто предположение о том, что не существует числа со свойством А, то найдется натуральное число со свойством А. [12]
А - перечислимые множества, где А есть последовательность, состоящая только из единиц, обычно называются рекурсивно-пере-числимыми множествами. [13]
Понятие рекурсивно перечислимого множества обобщается аналогично. Множество Е рекурсивно перечислимо, если имеется алгоритм перечисления его элементов. В исчислении предикатов и вообще в любой теории первого порядка теоремы всегда образуют рекурсивно перечислимое подмножество формул. Однако оно рекурсивно лишь в случае разрешимости теории. [14]
Для рекурсивно перечислимого множества X мно жество со X рекурсивно перечислимо тогда и только тогда, когда X рекурсивно. [15]