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

7. Доведіть рекурсивність оператора ( : F2\x2192F1, заданого умовою: 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\x2192F1, що задається наступною умовою:

\xF020\xF03F

\xF020\xF03F

\xF020\xF03F

\xF020\xF03F

\xF020\xF03F

\xF020\xF03F

\x2192Fп.

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) є РПМ.

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

.

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

. 1-1-екстенсійні функції назвемо просто екстенсійними.

.

). для кожного k(N.

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

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

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

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

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

.