Реферат на тему:
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)=.
Для ЧРО ,