Eфективні операції на функціях та множинах

Множину всіх n-арних функцій на N, тобто функцiй iз Nп в N, позначимо Fп. Об'єднання множин Fп для всіх п1 позначимо F. Множину всіх тотальних функцій із Fп та множину всіх тотальних функцій із F відповідно позначимо Tп та T . Cкінченні множини в цьому розділі позначаємо F, скінченні функції позначаємо .

Довільну функцію вигляду : (2N)m→2N назвемо m-арним множинним оператором (скорочено МО).

Довільну функцію вигляду Ψ: (F)m→F назвемо m-арним функціональним оператором (скорочено ФО).

Функціональні оператори називають також операціями на функціях, або композиціями.

Приклад. Операції суперпозиції Sn+1 : (F)m→F, примітивної рекурсії R : FF →F та мінімізації M : FF→F є прикладами ФО.

МО : (2N)m→2N називається монотонним, якщо із умови А1В1 , А2 В2 , ..., Ат Вт випливає (А1 , ..., Ап) (В1 , ..., Вп).

ФО : (F)m→F називається монотонним, якщо із умови f1 g1 , f2 g2 , ..., fт gт випливає (f1 , ..., fп) (g1 , ..., gп).

МО : (2N)m→2N називається неперервним, якщо для всіх хN, A(2N)m маємо х(A) FA : х(F).

ФО : Fп→F називається неперервним, якщо для всіх хNп, yN та fFп маємо (х, у)(f) f : (х, у)().

Легко довести, що кожний неперервний оператор є монотонним.

11.1. ОПЕРАТОРИ ПЕРЕЛІКУ. ЧАСТКОВО РЕКУРСИВНІ ТА РЕКУРСИВНІ ОПЕРАТОРИ

Ефективність множинного оператора : 2N→2N означає можли-вість ефективно задати множину (A), якщо ефективно задається множина А. Ефективні множинні оператори називаються [10] операторами переліку (скорочено ОП).

Для кожного zN оператор переліку z : 2N→2N задається співвідношенням z(A) ={x | u(Fu А C(x, u)Dz)}.

Інакше кажучи, xz(A) u(Fu А C(x, u)Dz).

Теорема 11.1.1. Кожний оператор переліку є неперервним та монотонним.

Множина АN однозначна, якщо С -1(А)={(l(x), r(x))} є функціо-нальним відношенням. Зрозуміло, що A однозначнa (Сm+1)-1(A) є функціональним відношенням для кожного m1. Отже, множина A однозначнa m1 fFm : A=Сm+1(f). Тому для множини всіх однозначних множин можна ввести наступне позначення:

CF ={С(f) | fF1}={Сm+1(f) | fFm}.

Кожний функціональний оператор : Fm→Fn задає множинний оператор : CF→CF та навпаки:

: Fm → Fn

Сm+1(Сm+1)-1 Сn+1(Сn+1)-1

: CF → CF

Звідси (f)=(Сn+1)-1((Сm+1(f))) та (A)=Сn+1(((Сm+1)-1(A))).

ФО : Fm→Fn називається частково рекурсивним оператором (ЧРО), якщо існує zN таке, що для всіх fFm маємо: