Реферат на тему:

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] операторами переліку (скорочено ОП).

Для кожного zN оператор переліку 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 маємо:

(f)=

В цьому випадку кажуть, що ОП z визначає ЧРО .

Тотальний ЧРО назвемо рекурсивним оператором (РО).

Інакше кажучи, ФО : Fm>Fn ??рекурсивний оператор, якщо

існує zN таке: для всіх fFm (f)=(Сn+1)-1(z(Сm+1(f))) (df1)

Дамо безпосереднє визначення РО, не використовуючи поняття оператора переліку. Вживатимемо скорочення для х1 , ..., хп.

ФО : Fm>Fn ??рекурсивний оператор, якщо

існує zN таке: для всіх fFm, (, у)Nп+1 маємо

(, у)(f) и(f у=(и,)) (df2)

Зрозуміло, що таке визначення РО еквівалентне наступному:

існує ЧРФ така: для всіх fFm, (, у)Nп+1 маємо

(, у)(f) и(f у=(и,)) (df3)

Теорема 11.1.2. Визначення df1, df2 та df3 еквівалентні.

Надалі для РО будемо, як правило, використовувати df3.

Теорема 11.1.3. Кожний РО є неперервним та монотонним.

Приклад 1. Нехай оператор : F1>F1 задається співвідношеням

Тоді немонотонний, отже, не РО.

Візьмемо скінченну f та нескінченну f. Тоді ()=f та (f)=f . Маємо f та (f)(). Отже, не є монотонним.

Приклад 2. Нехай оператор : F1>F1 задається співвідношеням

? Тоді не неперервний і не РО.

Візьмемо функцію f із нескінченною Еf (наприклад, f ? тотожна функція). Тоді (f)=ff та ()=f для кожної скінченної f. Тому якщо (х, у)(f), то не існує скінченної функції f такої, що (х, у)(), бо ()=f =. Отже, не є неперервним.

Для доведення рекурсивності операторів корисним є наступний критерій рекурсивності:

Теорема 11.1.4. Оператор : Fт>Fп є рекурсивним оператором неперервний та функція

є ЧРФ.

Розглянемо приклади використання теореми 11.1.4.

Приклад 3. Оператор : Fт>Fп задається умовою (f)=g для всіх fFт, де g ??фіксована ЧРФ. Тоді є РО.

Оператор неперервний: умова (, у)(f) (, у)() виконується для довільної скінченної f , адже (f)=()=g. Функція (и,)= є ЧРФ за ТЧ.

Приклад 4. Задамо оператор : F1>F1 таким співвідношенням: (f)(x)= f(f(x+2))+5x для всіх fF1. Тоді є РО.

Оператор неперервний: (х, у)(f) (х, у)() виконується для кожної скінченної f такої, що x+2D та f(x+2)D. Тепер

(и, х) =

є ЧРФ за ТЧ.

Приклад 5. Оператор мінімізації М: Fп+1>Fп задається умовою М(f)() = у(f(, у)=0) для всіх fFп+1. Тоді М є РО.

Оператор М неперервний: у=у(f(, у)=0) у=у((, у)=0) виконується для кожної f такої, що (, 0), (, 1), ..., (, у)D ; тому y=М(f)() y=М()() для кожної такої f. Тепер функція

(и,) = є ЧРФ за ТЧ.

Приклад 6. Нехай ФО 0 : F1>F1 задається співвідношенням 0({(0,0)})={(0,0)} та 0({(1,0)})={(0,1)}; для інших fF1 значення 0(f) невизначене. Тоді 0 розширюється до ЧРО та не розширюється до жодного РО.

Позаяк {C(0,0)}={0}=F1 та {C(1,0)}={2}=F4 , беремо z таке, що Dz ={C(0,20), C(1,22)}. Нехай ОП z задається таким Dz , тобто xz(A) u(Fu А C(x, u)Dz). Зрозуміло, що для кожних A 2N z(A) l(Dz)={0,1}. Маємо:

? якщо А та А, то z(A)={0,1};

??якщо А та А, то z(A)={0};

? якщо А та А, то z(A)={1};

? якщо 0А та 2А, то z(A)=.

Для ЧРО ,