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

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 : F(F ?F та мінімізації M : F(F?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) ( ( F(A : х(((F).

ФО (: Fп?F називається неперервним, якщо для всіх х(Nп, y(N та
f(Fп маємо (х, у)(((f) ( (( (f : (х, у)(((().

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

11.1. ОПЕРАТОРИ ПЕРЕЛІКУ. ЧАСТКОВО РЕКУРСИВНІ ТА РЕКУРСИВНІ ОПЕРАТОРИ

Ефективність множинного оператора (: 2N?2N означає можли-вість
ефективно задати множину ((A), якщо ефективно задається множина А.
Ефективні множинні оператори називаються [10] операторами переліку
(скорочено ОП).

Для кожного z(N оператор переліку (z : 2N?2N задається
співвідношенням (z(A) ={x | (u(Fu (А ( C(x, u)(Dz)}.

Інакше кажучи, x((z(A) ( (u(Fu (А ( C(x, u)(Dz).

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

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

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

Кожний функціональний оператор (: 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 називається частково рекурсивним оператором (ЧРО), якщо
існує z(N таке, що для всіх f(Fm маємо:

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

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

Інакше кажучи, ФО (: Fm?Fn ??рекурсивний оператор, якщо

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

для х1 , …, хп.

ФО (: Fm?Fn ??рекурсивний оператор, якщо

, у)(Nп+1 маємо

)) (df2)

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

, у)(Nп+1 маємо

)) (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)=f(f( та ((()=f( для кожної скінченної ((f.
Тому якщо (х, у)(((f), то не існує скінченної функції ((f такої, що
(х, у)((((), бо ((()=f( =(. Отже, ( не є неперервним.

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

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

є ЧРФ.

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

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

є ЧРФ за ТЧ.

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

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

є ЧРФ за ТЧ.

, у)=0) для всіх f(Fп+1. Тоді М є РО.

) для кожної такої ((f. Тепер функція

є ЧРФ за ТЧ.

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

Позаяк {C(0,0)}={0}=F1 та {C(1,0)}={2}=F4 , беремо z таке, що Dz
={C(0,20), C(1,22)}. Нехай ОП (z задається таким Dz , тобто
x((z(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)=(.

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

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

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

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

4) Якщо (0,0)(f та (1,0)(f, то 0(C(f) та 2(C(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(В).

теж монотонний

теж неперервний

теж рекурсивний

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

.

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, що задається наступною
умовою:

??

??

??

??

??

??

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

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

.

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

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

.

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

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

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

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

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

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

.

Враховуючи неперервність, доводимо, що А є ННТ оператора (. Якщо (
є оператором переліку, то доводиться, що 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 є ННТ оператора (. Якщо (
є рекурсивним оператором, то доводиться, що f є ЧРФ.

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

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

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

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

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

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

????

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

бо f1(х, у) невизначене при x>0.

= f1 .

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

????

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

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

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

????

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

ВПРАВИ

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

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

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

????

????

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

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

Похожие записи