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

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

Eфективні операції на функціях та множинах Множину всіх n-арних функцій на N, тобто функцiй iз Nп в N, позначимо Fп. Об'єднання множин Fп для всіх ппозначимо F. Множину всіх тотальних функцій із Fп та множину всіх тотальних функцій із F відповідно позначимо Tп та T. Cкінченні множини в цьому розділі позначаємо F, скінченні функції позначаємо p>

Довільну функцію вигляду 2N) m->2N назвемо m-арним множинним оператором (скорочено МО).

Довільну функцію вигляду) m->F назвемо m-арним функціональним оператором (скорочено ФО).

Функціональні оператори називають також операціями на функціях, або композиціями.

Приклад. Операції суперпозиції Sn+1: (F)m->F, примітивної рекурсії R: F->F та мінімізації M: F->F є прикладами ФО.

МО 2N) m->2N називається монотонним, якщо із умови А1, А2, …, Ат т випливає 1, …, Ап) (В1, …, Вп).

ФО F) m->F називається монотонним, якщо із умови f1, f2, …, fт випливає, …, fп) (g1, …, gп).

МО 2N) m->2N називається неперервним, якщо для всіх х A) m маємо х (A) х (F).

ФО п->F називається неперервним, якщо для всіх х, yта f маємо (х, у)(f) (х, у)(/p>

Легко довести, що кожний неперервний оператор є монотонним.

11.1. ОПЕРАТОРИ ПЕРЕЛІКУ. ЧАСТКОВО РЕКУРСИВНІ ТА РЕКУРСИВНІ ОПЕРАТОРИ Ефективність множинного оператора N->2N означає можли-вість ефективно задати множину, якщо ефективно задається множина А. Ефективні множинні оператори називаються [10] операторами переліку (скорочено ОП).

Для кожного zоператор переліку 2N->2N задається співвідношенням) ={x | u x, u)}.

Інакше кажучи, xz (A) u x, u).

Теорема 11.1.1. Кожний оператор переліку є неперервним та монотонним.

Множина Аоднозначна, якщо С -1(А)={(l (x), r (x))} є функціо-нальним відношенням. Зрозуміло, що A однозначнa Сm+1)-1(A) є функціональним відношенням для кожного m Отже, множина A однозначнa: A=Сm+1(f). Тому для множини всіх однозначних множин можна ввести наступне позначення:

CF ={С (f) | f={Сm+1(f) | f.

Кожний функціональний оператор m->Fn задає множинний оператор F->CF та навпаки:

Fm -> Fn.

Сm+1(Сm+1)-1 Сn+1(Сn+1)-1.

CF -> CF.

Звідси =(Сn+1)-1(m+1(f))) та =Сn+1(Сm+1)-1(A))).

ФО m->Fn називається частково рекурсивним оператором (ЧРО), якщо існує zтаке, що для всіх f маємо:

= $$\begin{array}{c}(C^{n+1}{)}^{-1}({}_z(C^{m+1}(f))),\text{якщо}{}_z(C^{\text{m+}1}(f))\text{однозначна,}\\ \text{невизначене інакше}\text{.}\\ \\ \begin{array}{c}\{\end{array}\hfill \\ \end{array}$$.

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

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

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

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

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

ФО m->Fn рекурсивний оператор, якщо.

існує zтаке: для всіх f ($$\stackrel{}{x}$$, у)+1 маємо.

($$\stackrel{}{x}$$, у)(f) ath xmlns="http://www.w3.org/1998/Math/MathML" display="block" >ит = $${}_z^{n+1}$$ (и, $$\stackrel{}{x}$$)) (df2).

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

існує ЧРФ така: для всіх f ($$\stackrel{}{x}$$, у)+1 маємо.

($$\stackrel{}{x}$$, у)(f) ath xmlns="http://www.w3.org/1998/Math/MathML" display="block" >ит =, $$\stackrel{}{x}$$)) (df3).

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

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

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

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

$$\begin{array}{c}g,\text{якщо}g\text{cкінченна,}\\ f_{\mathrm{}}\text{інакше}\text{.}\\ \\ (g)=\begin{array}{c}\{\end{array}\\ \end{array}$$ Тоді немонотонний, отже, не РО.

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

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

$$\begin{array}{c}g,\text{якщо}{E}_g\text{нескінченна,}\\ f_{\mathrm{}}\text{інакше}\text{.}\\ \\ (g)=\begin{array}{c}\{\end{array}\\ \end{array}$$ оді не неперервний і не РО.

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

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

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

$$\begin{array}{c}({}_u^m)(\stackrel{}{x}),\text{якщо}и\text{-}\text{код}\text{деякої}\text{скінченної}\text{функції},\\ \text{невизначене}\text{інакше},\\ \\ (u,\stackrel{}{x})=\begin{array}{c}\{\end{array}\\ \end{array}$$ є ЧРФ.

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

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

Оператор неперервний: умова ($$\stackrel{}{x}$$, у)(f) $$\stackrel{}{x}$$, у)(виконується для довільної скінченної f, адже =. Функція, $$\stackrel{}{x}$$)= $$\begin{array}{c}g(\stackrel{}{x}),\text{якщо}и\text{— код деякої скінченної функції,}\\ \text{невизначене інакше,}\\ \\ \begin{array}{c}\{\end{array}\hfill \\ \end{array}$$ є ЧРФ за ТЧ.

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

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

х) = $$\begin{array}{c}{}_u({}_u(x+2))+\mathrm{5,}\text{якщо}u-\text{код деякої скінченної функції,}\\ \text{невизначене інакше,}\\ \\ \begin{array}{c}\{\end{array}\hfill \\ \end{array}$$.

є ЧРФ за ТЧ.

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

Оператор М неперервний: у=f ($$\stackrel{}{x}$$, у)=0) =math xmlns="http://www.w3.org/1998/Math/MathML" display="block" >x, у)=0) виконується для кожної f такої, що ($$\stackrel{}{x}$$, 0), ($$\stackrel{}{x}$$, 1), …, ($$\stackrel{}{x}$$, у) тому y=М (f)($$\stackrel{}{x}$$) М ($$\stackrel{}{x}$$) для кожної такої f. Тепер функція.

$$\stackrel{}{x}$$) = $$\begin{array}{c}{}_y({}_u^{n+1}(\stackrel{}{x},y)=0),\text{якщо}u-\text{код деякої скінченної функції,}\\ \text{невизначене інакше,}\\ \\ \begin{array}{c}\{\end{array}\hfill \\ \end{array}$$ є ЧРФ за ТЧ.

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

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

кщо, А та А, то)={0,1};

якщо, А та А, то)={0};

кщо, А та А, то)={1};

кщо 0 та 2 то)=p>

Для ЧРО який визначається таким ОП маємо:

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

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

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

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

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

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

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

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

ЧРО називають загальнорекурсивним оператором (ЗРО), якщо Tт та т) Теорема 11.1.5. Нехай ЧРО т->Fп такий, що Tт Тоді є РО.

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

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

ВПРАВИ.

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

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

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

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

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

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

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

1) (x) = $$\underset{t<=x}{}f(2t)$$ -. 2) (x) = $$\underset{t<=2x}{}f(t)$$ .

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

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

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

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

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

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

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

1) $$\begin{array}{c}g,\text{якщо}{E}_g{D}_g\text{cкінченна,}\\ f_{\mathrm{}}\text{інакше}\\ \\ (g)=\begin{array}{c}\{\end{array}\\ \end{array}$$.

2) $$\begin{array}{c}g,\text{якщо}{E}_g{D}_g\text{неcкінченна,}\\ f_{\mathrm{}}\text{інакше}\\ \\ (g)=\begin{array}{c}\{\end{array}\\ \end{array}$$.

3) $$\begin{array}{c}g,\text{якщо}{E}_g{D}_g\text{cкінченна,}\\ f_{\mathrm{}}\text{інакше}\\ \\ (g)=\begin{array}{c}\{\end{array}\\ \end{array}$$.

4) $$\begin{array}{c}g,\text{якщо}{E}_g{D}_g\text{неcкінченна,}\\ f_{\mathrm{}}\text{інакше}\\ \\ (g)=\begin{array}{c}\{\end{array}\\ \end{array}$$.

5) $$\begin{array}{c}\\ g,\text{якщо}{D}_{g}g\text{cкінченна,}\\ f_{\mathrm{}}\text{інакше}\\ \\ (g)=\begin{array}{c}\{\end{array}\\ \end{array}$$.

6) $$\begin{array}{c}\\ g,\text{якщо}{E}_{g}g\text{неcкінченна,}\\ f_{\mathrm{}}\text{інакше}\\ \\ (g)=\begin{array}{c}\{\end{array}\\ \end{array}$$.

9. Сформулюйте визначення п-арного неперервного функціональ-ного оператора вигляду $${}^{{п}_1}$$ $${}^{{п}_1}$$ math xmlns="http://www.w3.org/1998/Math/MathML" display="block" >пт ->Fп.

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

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

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

11.2. ТЕОРЕМА МАЙХІЛЛА-ШЕПЕРДСОНА. ТЕОРЕМИ ПРО НЕРУХОМУ ТОЧКУ Кожний ОП при обмеженні на РПМ задає на їх індексах ефективну операцію, тобто рекурсивну функцію.

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

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

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

Теорема 11.2.2 (Майхілл, Шепердсон). Для кожного РО т->Fп існує РФ h така: для кожного kмаємо math xmlns="http://www.w3.org/1998/Math/MathML" display="block" >km)= $${}_{h(k)}^n$$ .

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

Функція h m-n-екстенсійна, якщо з умови $${}_k^m={}_l^m$$ випливає $${}_{h(k)}^n={}_{h(l)}^n$$. 1−1-екстенсійні функції назвемо просто екстенсійними.

Приклад 1. РФ h із теореми 11.2.2 m-n екстенсійна. Справді, з умови $${}_k^m={}_l^m$$ випливає $${}_{h(k)}^n=({}_k^m)=({}_l^m)={}_{h(l)}^n$$ .

Теорема 11.2.3 (Майхілл, Шепердсон). Для кожної m-n-екстенсій-ної РФ h існує єдиний РО т->Fп такий, що math xmlns="http://www.w3.org/1998/Math/MathML" display="block" >km)= $${}_{h(k)}^n$$). для кожного k.

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

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

2) якщо =B, то A тобто A айменша НТ оператора p>

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

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

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

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

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

1) =f, тобто f ерухома точка оператора /p>

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

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

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

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

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

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

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

Нехай РО 1->F1 визначений ОП для всіх f маємо =С-1(С (f))). Нехай, А є НТ оператора А=А). Тоді функція f =С-1(А) є нерухомою точкою РО =С-1(С (f)))= =С-1(А))=С-1(А)=f. З іншого боку, нехай f Т РО =f. Тоді множина А=С (f) Т оператора С (f))=С ()=С (f).

Приклад 4. Для ЧРО не РО найменшої нерухомої точки може не існувати. Це буває тоді, коли множина А, що є НТ відповідного ОП еоднозначна. Тоді кожна В неоднозначна, тому такий взагалі не має нерухомих точок.

Приклад 5. Знайдемо ННТ оператора F1->F1, заданого умовою.

$$\begin{array}{c}\mathrm{1,}\text{якщо}х=0\text{,}\\ f(x+1),\text{якщо}х>0\text{.}\\ \\ (f)(х)=\begin{array}{c}\{\end{array}\\ \end{array}$$.

Оператор неперервний: (х, у)(f) х, у)(виконується при х=0 для довільної скінченної f, при х>0 ця умова викону-ється для кожної скінченної f такої, що x+1 Отже, має ННТ fH, яку знайдемо методом послідовних наближень.

Маємо f0=fТепер знаходимо f1 та f2:

f1(х)=)(х) = $$\begin{array}{c}\mathrm{1,}\text{якщо}х=0\text{,}\\ f_0(x+1),\text{якщо}х>\mathrm{0,}\\ \\ \begin{array}{c}\{\end{array}\hfill \\ \end{array}$$ = $$\begin{array}{c}\mathrm{1,}\text{якщо}х=0\text{,}\\ \text{невизначене},\text{якщо}х>0\text{.}\\ \\ \begin{array}{c}\{\end{array}\hfill \\ \end{array}$$.

f2(х)=)(х) = $$\begin{array}{c}\mathrm{1,}\text{якщо}х=0\text{,}\\ f_1(x+1),\text{якщо}х>\mathrm{0,}\\ \\ \begin{array}{c}\{\end{array}\hfill \\ \end{array}$$ = $$\begin{array}{c}\mathrm{1,}\text{якщо}х=0\text{,}\\ \text{невизначене},\text{якщо}х>0\text{.}\\ \\ \begin{array}{c}\{\end{array}\hfill \\ \end{array}$$.

Отже, f2 = f1. Маємо стабілізацію, тому fп = f1 для всіх n>0. Звідси ННТ fH $$=\underset{n>=0}{}{f}_n$$ = f1. Зауважимо, що інші нерухомі точки нашого оператора мають вигляд fТ (х) = $$\begin{array}{c}\mathrm{1,}\text{якщо}х=0\text{,}\\ a,\text{якщо}х>0\text{.}\\ \\ \begin{array}{c}\{\end{array}\hfill \\ \end{array}$$.

Приклад 6. Знайдемо ННТ оператора F2->F2, заданого умовою.

$$\begin{array}{c}\mathrm{0,}\text{якщо}х=0\text{,}\\ f(x-\mathrm{1,}f(x,y)),\text{якщо}х>0\text{.}\\ \\ (f)(х,y)=\begin{array}{c}\{\end{array}\\ \end{array}$$.

Оператор неперервний: умова (х, у, z)(f) х, у, z)(виконується при х=0 для довільної скінченної f, при х>0 ця умова виконується для кожної скінченної f такої, що (х, у) та (хf (х, у)) Отже, має ННТ fH, яку знайдемо методом послідовних наближень. Маємо f0=fТепер знаходимо f1 та f2:

f1(х, у) =)(х, у)) = $$\begin{array}{c}\mathrm{0,}\text{якщо}х=0\text{,}\\ f_0(x-\mathrm{1,}{f}_0(x,y)),\text{якщо}х>\mathrm{0,}\\ \\ \begin{array}{c}\{\end{array}\hfill \\ \end{array}$$ = = $$\begin{array}{c}\mathrm{1,}\text{якщо}х=0\text{,}\\ \text{невизначене},\text{якщо}х>0\text{.}\\ \\ \begin{array}{c}\{\end{array}\hfill \\ \end{array}$$.

f2(х, у) =)(х, у)) = $$\begin{array}{c}\mathrm{0,}\text{якщо}х=0\text{,}\\ f_1(x-\mathrm{1,}{f}_1(x,y)),\text{якщо}х>\mathrm{0,}\\ \\ \begin{array}{c}\{\end{array}\hfill \\ \end{array}$$ = = $$\begin{array}{c}\mathrm{1,}\text{якщо}х=0\text{,}\\ \text{невизначене},\text{якщо}х>\mathrm{0,}\\ \\ \begin{array}{c}\{\end{array}\hfill \\ \end{array}$$ бо f1(х, у) невизначене при x>0.

Отже, f2 = f1. Маємо стабілізацію, тому fп = f1 для всіх n>0. Звідси ННТ fH $$=\underset{n>=0}{}{f}_n$$ = f1 .

Приклад 7. Знайдемо ННТ оператора F1->F1, заданого умовою.

$$\begin{array}{c}\mathrm{0,}\text{якщо}х=0\text{,}\\ 2x-1+f(x-1),\text{якщо}х>0\text{.}\\ \\ (f)(х)=\begin{array}{c}\{\end{array}\\ \end{array}$$.

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

Метод послідовних наближень тут вимагає нескінченної кількості кроків, бо fп+1 п для всіх n Тому використаємо обхідні шляхи. Нехай fH НТ нашого оператора. Тоді для кожного хмаємо fН (х)=Н)(х) = 2хfН (х= 2хН)(х= 2ххН (х= … = 2хх… +1+fН (0) = 2хх… +1+0 = х2. Отже, для всіх х fН (х) = х2. Тому така fH дина нерухома точка нашого p>

Приклад 8. Знайдемо ННТ оператора F1->F1, заданого умовою.

$$\begin{array}{c}х-\mathrm{6,}\text{якщо}х>\text{55}\text{,}\\ f(f(x+7))\text{при}х<=\text{55}\text{.}\\ \\ (f)(х)=\begin{array}{c}\{\end{array}\\ \end{array}$$.

Оператор неперервний: (х, у)(f) х, у)(виконується при х>55 для довільної скінченної f, при х умова викону-ється для кожної скінченної f такої, що x+7та f (x+7) Отже, має ННТ, нехай це функція fH. Для кожного х>55 маємо fН (x)=Н)(х) = х Тепер fН (55)=Н)(55) = fН (fН (62)) = fН (56) = 50. Тоді fН (54)=Н)(54) = fН (fН (61)) = fН (55) = 50. Продовжуючи далі, аналогічно дістаємо fН (53) = fН (54) = 50, …, fН (0) = fН (1) = 50. Отже, fH дина нерухома точка оператора причому така fH має вигляд.

fН (x) = $$\begin{array}{c}х-\mathrm{6,}\text{якщо}х>\text{55}\text{,}\\ \text{50},\text{якщо}х<=\text{55}\text{.}\\ \\ \begin{array}{c}\{\end{array}\hfill \\ \end{array}$$.

ВПРАВИ.

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

1) $$\begin{array}{c}\mathrm{1,}\text{якщо}х=0\text{,}\\ 3x+f(x-1)\text{при}х>0-\\ \\ (f)(х)=\begin{array}{c}\{\end{array}\\ \end{array}$$.

2) $$\begin{array}{c}\mathrm{2,}\text{якщо}х=0\text{,}\\ 2x+5+f(x-1)\text{при}х>0\text{-}\\ \\ (f)(х)=\begin{array}{c}\{\end{array}\\ \end{array}$$.

3) $$\begin{array}{c}\mathrm{3,}\text{якщо}х=0\text{,}\\ 4x+1+f(x-1)\text{при}х>0\text{-}\\ \\ (f)(х)=\begin{array}{c}\{\end{array}\\ \end{array}$$.

4) $$\begin{array}{c}\mathrm{4,}\text{якщо}х=0\text{,}\\ 3f(x-1)\text{при}х>0\text{-}\\ \\ (f)(х)=\begin{array}{c}\{\end{array}\\ \end{array}$$.

5) $$(f)(х)=\{\begin{array}{c}\mathrm{0,}\text{якщо}х=\mathrm{0,}\\ \mathrm{1,}\text{якщо}х=\mathrm{1,}\\ f(x-1)+f(x-2),\text{якщо}х>1\text{.}\end{array}$$.

2. Доведіть рекурсивність та знайдіть ННТ оператора 2->F2, заданого наступною умовою:

1) $$\begin{array}{c}\mathrm{5,}\text{якщо}х=0\text{,}\\ f(x+\mathrm{2,}f(x-\mathrm{1,}y+3))\text{при}х>0\text{-}\\ \\ (f)(х,y)=\begin{array}{c}\{\end{array}\\ \end{array}$$.

2) $$\begin{array}{c}\mathrm{3,}\text{якщо}х=0\text{,}\\ f(x-\mathrm{1,}f(x+\mathrm{3,}y+2))\text{при}х>0\text{-}\\ \\ (f)(х,y)=\begin{array}{c}\{\end{array}\\ \end{array}$$.

3) $$\begin{array}{c}\mathrm{2,}\text{якщо}х=0\text{,}\\ f(x+\mathrm{3,}f(x-\mathrm{1,}2y+1))\text{при}х>0\text{.}\\ \\ (f)(х,y)=\begin{array}{c}\{\end{array}\\ \end{array}$$.

3. Доведіть рекурсивність та знайдіть ННТ оператора 1->F1, заданого наступною умовою:

1) $$\begin{array}{c}х-\mathrm{8,}\text{якщо}х>=\text{60}\text{,}\\ f(f(x+9))\text{при}х<\text{60}-\\ \\ (f)(х)=\begin{array}{c}\{\end{array}\\ \end{array}$$.

2) $$\begin{array}{c}х-\text{10},\text{якщо}х>\text{100}\text{,}\\ f(f(x+\text{11}))\text{при}х<=\text{100}\text{.}\\ \\ (f)(х)=\begin{array}{c}\{\end{array}\\ \end{array}$$.

4. Сформулюйте та доведіть для випадку п-арних операторів відпо-відні узагальнення теорем 11.2.1 — 11.2.3.

5. Нехай та рекурсивні оператори F1-> F1. Доведіть, що існує найменша пара функцій f, g така, що f= g) та g= g), причому функцїї f та g є ЧРФ.