1) Якщо (0,0)f та (1,0)f, то 0C(f) та 2C(f), звідки z(C(f))=. Отже, для таких f (f)=f .

2) Якщо (0,0)f та (1,0)f, то 0C(f) та 2C(f), звідки z(C(f))={0}=C(0,0). Отже, для таких f (f)={(0,0)};

3) Якщо (0,0)f та (1,0)f, то 0C(f) та 2C(f), звідки z(C(f))={1}=C(0,1). Отже, для таких f (f)={(0,1)};

4) Якщо (0,0)f та (1,0)f, то 0C(f) та 2C(f), звідки z(C(f))={0,1} ? неоднозначна множина. Отже, для таких f (f) невизначене, тому не РО.

Із 2) та 3) випливає, що ЧРО є розширенням оператора 0 .

Нехай ={(0,0), (1,0)}. Для довільного ЧРО , що є розширенням 0 , маємо: якщо (), то ()({(0,0)})=0({(0,0)})={(0,0)} та ()({(1,0)})=0({(1,0)})={(0,1)}. Але тоді () як множина не є функція, тобто (). Отже, кожний такий ЧРО нетотальний, тобто не РО. Таким чином, 0 не можна розширити до РО.

Приклад 7. ЧРО із прикладу 6 немонотонний.

Для ={(0,0), (1,0)} маємо (), але ({(0,0)})={(0,0)}. Тому з умови {(0,0)} не випливає ({(0,0)}().

ЧРО називають загальнорекурсивним оператором (ЗРО), якщо Tт D та (Tт)Fn.

Теорема 11.1.5. Нехай ЧРО : Fт>Fп такий, що TтD . Тоді є РО.

Наслідок. Для класів ЗРО, РО та ЧРО маємо строгі включення ЗРОРОЧРО.

За теоремою 11.1.5 ЗРОРО. Але РО прикладу 3 не є, очевидно, ЗРО, якщо ЧРФ g взяти нетотальною, тобто не РФ. За визначенням РОЧРО. Але ЧРО із прикладу 6 немонотонний, тому не РО.

ВПРАВИ

1. Нехай z ? оператор переліку. Дослідити співвідношення:

1) між множинами z(АВ) та z(А)z(В);

2) між множинами z(АВ) та z(А)z(В).

2. Нехай та ? монотонні оператори (тут та ? 1-арні МО або ФО вигляду : Fт>Fр та : Fр>Fп). Доведіть, що оператор теж монотонний

3. Нехай та ? неперервні оператори (тут та ? 1-арні МО або ФО вигляду : Fт>Fр та : Fр>Fп). Доведіть, що оператор теж неперервний

4. Нехай та ? рекурсивні оператори вигляду : Fт>Fр та : Fр>Fп. Доведіть, що оператор теж рекурсивний

5. Доведіть рекурсивність оператора : F1>F1, заданого умовою:

1) (f)(x) = ;. 2) (f)(x) = .

6. Доведіть рекурсивність оператора : F1>F1, заданого так:

1) (f)(x) = f(f(f(x+1)))+x; 2) (f)(x) = f(f(x2+3))+2x;

3) (f)(x) = (f(f(3x)))2+3x; 4) (f)(x) = f(f(7x+5)))+f(f(f(x))).

7. Доведіть рекурсивність оператора : F2>F1, заданого умовою: 1) (f)(x) = f(x, x);

2) (f)(x) = f(f(2x, x), f(x, 3x));

3) (f)(x) = f(f(x, x)+1, f(3x, x)+2)+3.

8. Чи буде рекурсивним оператор : F1>F1, що задається наступною умовою:

1) ??

2) ??

3) ??

4) ??

5) ??

6) ??

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

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

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

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

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

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

Теорема 11.2.1. Існує РФ s така, що для всіх z, yN маємо 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}nN так: A0=; An+1=(An) для n0. Покладемо .

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

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

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

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

Приклад 2. Нехай ННТ f оператора є тотальною функцією. Тоді f ? єдина нерухома точка оператора .

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

Теорема 11.2.5 (С.Кліні). 1) Кожний неперервний ФО : Fп>Fп має найменшу нерухому точку;

2) якщо є РО, то його ННТ є ЧРФ.

Функцію f, що є ННТ оператора , будуємо методом послідовних наближень. Задамо послідовність функцій {fn}nN так: f0=f; fn+1=(fn) для n0. Покладемо .

Враховуючи неперервність, доводимо, що f є ННТ оператора . Якщо є рекурсивним оператором, то доводиться, що f є ЧРФ.

Нехай РО : F1>F1 визначений ОП z : для всіх fF1 маємо (f)=С-1(z (С(f))). Нехай А є НТ оператора z : А=z