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

9. Сформулюйте визначення п-арного неперервного функціональ-ного оператора вигляду : F ... F ...F →Fп.

10. Сформулюйте визначення п-арного оператора переліку, п-арного ЧРО, п-арного РО та п-арного ЗРО.

11. Сформулюйте та доведіть для випадку п-арних операторів відпо-відні узагальнення теорем 11.1.1 – 11.1.5.

12. Доведіть рекурсивність операторів примітивної рекурсії R та суперпозиції Sn+1.

11.2. ТЕОРЕМА МАЙХІЛЛА-ШЕПЕРДСОНА. ТЕОРЕМИ ПРО НЕРУХОМУ ТОЧКУ

Кожний ОП при обмеженні на РПМ задає на їх індексах ефективну операцію, тобто рекурсивну функцію.

Теорема 11.2.1. Існує РФ s така, що для всіх z, yN маємо z(Dy)=Ds(x,y)..

Наслідок. Нехай А є РПМ. Тоді z(A) є РПМ.

Кожний РО при обмеженні на ЧРФ задає на їх індексах ефективну операцію, тобто рекурсивну функцію.

Теорема 11.2.2 (Майхілл, Шепердсон). Для кожного РО : Fт→Fп існує РФ h така: для кожного kN маємо ( )=

Наслідок. Нехай є РО, f є ЧРФ. Тоді (f) є ЧРФ.

Функція h m-n-екстенсійна, якщо з умови випливає . 1-1-екстенсійні функції назвемо просто екстенсійними.

Приклад 1. РФ h із теореми 11.2.2 m-n екстенсійна. Справді, з умови випливає .

Теорема 11.2.3 (Майхілл, Шепердсон). Для кожної m-n-екстенсій-ної РФ h існує єдиний РО : Fт→Fп такий, що ( )= ). для кожного kN.

Множина А називається найменшою нерухомою точкою (ННТ) оператора : 2N→2N , якщо:

1) (A)=A, тобто A нерухома точка (НТ) оператора ;

2) якщо (B)=B, то AB; тобто A  найменша НТ оператора.

Теорема 11.2.4 (С.Кліні). 1) Кожний неперервний множинний оператор : 2N→2N має найменшу нерухому точку;

2) якщо є оператором переліку, то його ННТ є РПМ.

Множину A, що є ННТ оператора будуємо методом послідовних наближень. Задамо послідовність множин {An}nN так: A0=; An+1=An) для n0. Покладемо .

Враховуючи неперервність, доводимо, що А є ННТ оператора Якщо є оператором переліку, то доводиться, що A є РПМ.

Функція f називається найменшою нерухомою точкою оператора : Fп→Fп, якщо:

1) (f)=f, тобто f  нерухома точка оператора ;

2) якщо (g)=g, то f g; тобто f найменша НТ оператора

\Приклад 2. Нехай ННТ f оператора є тотальною функцією. Тоді f єдина нерухома точка оператора .Приклад 3. Найменша нерухома точка тотожного оператора це f. Тотожний оператор є ЗРО. Отже, для ЗРО найменша нерухома точка може бути нетотальною функцією.