ПЕРЕЧИСЛЕНИЯ ОПЕРАТОР

отображение множества всех множеств натуральных чисел в себя (т. е. отображение 2^N в 2^N , где N - множество натуральных чисел), определяемое следующим образом. Пусть W_z - рекурсивно перечислимое множество с гёделевым номером z, D_u - конечное множество натуральных чисел с канонич. индексом и(то есть D_u= {x₁ х ₂, . . ., х _п}, где x₁<x₂<...<х _n и 2^x1+2^x2...+2^xn=u), <x, u> - номер упорядоченной пары, состоящей из чисел хи и, при нек-ром фиксированном взаимно однозначном рекурсивном кодировании пар. С каждым рекурсивно перечислимым множеством W_z связана процедура, преобразующая любое множество натуральных чисел Вв нек-рое множество натуральных чисел А. А именно, если число < х, u> принадлежит множеству W_z и конечное множество D_u содержится в множестве В, то хотносится к множеству А. Иными словами,

Эта процедура позволяет из любого пересчета множества Вэффективно получить пересчет множества А. Она наз. П. о. и обозначается Ф _z. Если для нек-рого П. о. Yимеет место Y(B)=A, то говорят, что А с в о-д и т с я по перечислимости к

Если Ф и Y суть П. о., то их композиция ФY также есть П. о. Если Y - П. о. и , то Если , то для нек-рого конечного множества . Каждый П. о. Y имеет неподвижную точку, а именно, существует такое рекурсивно перечислимое множество А , что Y(А)=А , и если Y(В)=В, то

Лит.:[1] Роджерс X., Теория рекурсивных функций и эффективная вычислимость, пер. с англ., М., 1972. В. Е. Плиско.