Перечисления Оператор
отображение множества всех множеств натуральных чисел в себя (т. Е. Отображение 2N в 2N , где N - множество натуральных чисел), определяемое следующим образом. Пусть Wz - рекурсивно перечислимое множество с гёделевым номером z, Du - конечное множество натуральных чисел с канонич. Индексом и(то есть Du= {x1 х 2, . ., х п}, где x1<x2<...<х n и 2x1+2x2...+2xn=u), <x, u>. - номер упорядоченной пары, состоящей из чисел хи и, при нек-ром фиксированном взаимно однозначном рекурсивном кодировании пар. С каждым рекурсивно перечислимым множеством Wz связана процедура, преобразующая любое множество натуральных чисел Вв нек-рое множество натуральных чисел А. А именно, если число <. Х, u>. Принадлежит множеству Wz и конечное множество Du содержится в множестве В, то хотносится к множеству А.
Иными словами, Эта процедура позволяет из любого пересчета множества Вэффективно получить пересчет множества А. Она наз. П. О. И обозначается Ф z. Если для нек-рого П. О. Yимеет место Y(B)=A, то говорят, что А с в о-д и т с я по перечислимости к Если Ф и Y суть П. О., то их композиция ФY также есть П. О. Если Y - П. О. И , то Если , то для нек-рого конечного множества . Каждый П. О. Y имеет неподвижную точку, а именно, существует такое рекурсивно перечислимое множество А , что Y(А)=А , и если Y(В)=В, то Лит.:[1] Роджерс X., Теория рекурсивных функций и эффективная вычислимость, пер. С англ., М., 1972. В. Е. Плиско.
Дополнительный поиск Перечисления Оператор
На нашем сайте Вы найдете значение "Перечисления Оператор" в словаре Математическая энциклопедия, подробное описание, примеры использования, словосочетания с выражением Перечисления Оператор, различные варианты толкований, скрытый смысл.
Первая буква "П". Общая длина 21 символа