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 маємо:
?(f)=EMBED Equation.3
В цьому випадку кажуть, що ОП ?z визначає ЧРО ?.
Тотальний ЧРО назвемо рекурсивним оператором (РО).
Інакше кажучи, ФО ?: Fm>Fn ??рекурсивний оператор, якщо
існує z?N таке: для всіх f?Fm ?(f)=(Сn+1)-1(?z(Сm+1(f))) (df1)
Дамо безпосереднє визначення РО, не використовуючи поняття оператора переліку. Вживатимемо скорочення EMBED Equation.3 для х1 , ..., хп.
ФО ?: Fm>Fn ??рекурсивний оператор, якщо
існує z?N таке: для всіх f?Fm, (EMBED Equation.3, у)?Nп+1 маємо
(EMBED Equation.3, у)??(f) ? ?и(?EMBED Equation.3?f ? у=EMBED Equation.3(и,EMBED Equation.3)) (df2)
Зрозуміло, що таке визначення РО еквівалентне наступному:
існує ЧРФ ? така: для всіх f?Fm, (EMBED Equation.3, у)?Nп+1 маємо
(EMBED Equation.3, у)??(f) ? ?и(?EMBED Equation.3?f ? у=?(и,EMBED Equation.3)) (df3)
Теорема 11.1.2. Визначення df1, df2 та df3 еквівалентні.
Надалі для РО будемо, як правило, використовувати df3.
Теорема 11.1.3. Кожний РО є неперервним та монотонним.
Приклад 1. Нехай оператор ?: F1>F1 задається співвідношеням
EMBED Equation.3 Тоді ? немонотонний, отже, не РО.
Візьмемо скінченну ??f? та нескінченну f??. Тоді ?(?)=??f? та ?(f)=f? . Маємо f?? та ?(f)??(?). Отже, ? не є монотонним.
Приклад 2. Нехай оператор ?: F1>F1 задається співвідношеням
EMBED Equation.3? Тоді ? не неперервний і не РО.
Візьмемо функцію f із нескінченною Еf (наприклад, f ? тотожна функція). Тоді ?(f)=f?f? та ?(?)=f? для кожної скінченної ??f. Тому якщо (х, у)??(f), то не існує скінченної функції ??f такої, що (х, у)??(?), бо ?(?)=f? =?. Отже, ? не є неперервним.
Для доведення рекурсивності операторів корисним є наступний критерій рекурсивності:
Теорема 11.1.4. Оператор ?: Fт>Fп є рекурсивним оператором ? ? неперервний та функція
EMBED Equation.3 є ЧРФ.
Розглянемо приклади використання теореми 11.1.4.
Приклад 3. Оператор ?: Fт>Fп задається умовою ?(f)=g для всіх f?Fт, де g ??фіксована ЧРФ. Тоді ? є РО.
Оператор ? неперервний: умова (EMBED Equation.3, у)??(f) ? (EMBED Equation.3, у)??(?) виконується для довільної скінченної ??f , адже ?(f)=?(?)=g. Функція ?(и,EMBED Equation.3)=EMBED Equation.3 є ЧРФ за ТЧ.
Приклад 4. Задамо оператор ?: F1>F1 таким співвідношенням: ?(f)(x)= f(f(x+2))+5x для всіх f?F1. Тоді ? є РО.
Оператор ? неперервний: (х, у)??(f) ? (х, у)??(?) виконується для кожної скінченної ??f такої, що x+2?D? та f(x+2)?D?. Тепер
?(и, х) =EMBED Equation.3
є ЧРФ за ТЧ.
Приклад 5. Оператор мінімізації М: Fп+1>Fп задається умовою М(f)(EMBED Equation.3) = ?у(f(EMBED Equation.3, у)=0) для всіх f?Fп+1. Тоді М є РО.
Оператор М неперервний: у=?у(f(EMBED Equation.3, у)=0) ? у=?у(?(EMBED Equation.3, у)=0) виконується для кожної ??f такої, що (EMBED Equation.3, 0), (EMBED Equation.3, 1), ..., (EMBED Equation.3, у)?D? ; тому y=М(f)(EMBED Equation.3) ? y=М(?)(EMBED Equation.3) для кожної такої ??f. Тепер функція
?(и,EMBED Equation.3) =EMBED Equation.3 є ЧРФ за ТЧ.
Приклад 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(В).
2. Нехай ? та ? ? монотонні оператори (тут ? та ? ? 1-арні МО або ФО вигляду ?: Fт>Fр та ?: Fр>Fп). Доведіть, що оператор EMBED Equation.3 теж монотонний
3. Нехай ? та ? ? неперервні оператори (тут ? та ? ? 1-арні МО або ФО вигляду ?: Fт>Fр та ?: Fр>Fп). Доведіть, що оператор EMBED Equation.3 теж неперервний
4. Нехай ? та ? ? рекурсивні оператори вигляду ? : Fт>Fр та ? : Fр>Fп. Доведіть, що оператор EMBED Equation.3 теж рекурсивний
5. Доведіть рекурсивність оператора ? : F1>F1, заданого умовою:
1) ?(f)(x) = EMBED Equation.3;. 2) ?(f)(x) = EMBED Equation.3.
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) EMBED Equation.3??
2) EMBED Equation.3??
3) EMBED Equation.3??
4) EMBED Equation.3??
5) EMBED Equation.3??
6) EMBED Equation.3??
9. Сформулюйте визначення п-арного неперервного функціональ-ного оператора вигляду ?: FEMBED Equation.3?...? FEMBED Equation.3?...?FEMBED Equation.3>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 така: для кожного k?N маємо ?(EMBED Equation.3)=EMBED Equation.3.
Наслідок. Нехай ? є РО, f є ЧРФ. Тоді ?(f) є ЧРФ.
Функція h m-n-екстенсійна, якщо з умови EMBED Equation.3 випливає EMBED Equation.3. 1-1-екстенсійні функції назвемо просто екстенсійними.
Приклад 1. РФ h із теореми 11.2.2 m-n екстенсійна. Справді, з умови EMBED Equation.3 випливає EMBED Equation.3.
Теорема 11.2.3 (Майхілл, Шепердсон). Для кожної m-n-екстенсій-ної РФ h існує єдиний РО ?: Fт>Fп такий, що ?(EMBED Equation.3)=EMBED Equation.3). для кожного k?N.
Множина А називається найменшою нерухомою точкою (ННТ) оператора ?: 2N>2N , якщо:
1) ?(A)=A, тобто A ? нерухома точка (НТ) оператора ? ;
2) якщо ?(B)=B, то A?B; тобто A ? найменша НТ оператора ?.
Теорема 11.2.4 (С.Кліні). 1) Кожний неперервний множинний оператор ?: 2N>2N має найменшу нерухому точку;
2) якщо ? є оператором переліку, то його ННТ є РПМ.
Множину A, що є ННТ оператора ?, будуємо методом послідовних наближень. Задамо послідовність множин {An}n?N так: A0=?; An+1=?(An) для n?0. Покладемо EMBED Equation.3.
Враховуючи неперервність, доводимо, що А є ННТ оператора ?. Якщо ? є оператором переліку, то доводиться, що 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}n?N так: f0=f?; fn+1=?(fn) для n?0. Покладемо EMBED Equation.3.
Враховуючи неперервність, доводимо, що 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, заданого умовою
EMBED Equation.3
Оператор ? неперервний: (х, у)??(f) ? (х, у)??(?) виконується при х=0 для довільної скінченної ??f, при х>0 ця умова викону-ється для кожної скінченної ??f такої, що x+1?D? . Отже, ? має ННТ fH , яку знайдемо методом послідовних наближень.
Маємо f0=f?. Тепер знаходимо f1 та f2:
f1(х)=?(f0)(х) =EMBED Equation.3 =EMBED Equation.3
f2(х)=?(f1)(х) =EMBED Equation.3 =EMBED Equation.3
Отже, f2 = f1. Маємо стабілізацію, тому fп = f1 для всіх n>0. Звідси ННТ fHEMBED Equation.3= f1 . Зауважимо, що інші нерухомі точки нашого оператора мають вигляд fТ(х) =EMBED Equation.3
Приклад 6. Знайдемо ННТ оператора ? : F2>F2, заданого умовою
EMBED Equation.3????
Оператор ? неперервний: умова (х, у, z)??(f) ? (х, у, z)??(?) виконується при х=0 для довільної скінченної ??f, при х>0 ця умова виконується для кожної скінченної ??f такої, що (х, у)?D? та (х?1, f(х, у))?D? . Отже, ? має ННТ fH , яку знайдемо методом послідовних наближень. Маємо f0=f?. Тепер знаходимо f1 та f2:
f1(х, у) =?(f0)(х, у)) =EMBED Equation.3 = =EMBED Equation.3
f2(х, у) =?(f1)(х, у)) =EMBED Equation.3 = =EMBED Equation.3 бо f1(х, у) невизначене при x>0.
Отже, f2 = f1 . Маємо стабілізацію, тому fп = f1 для всіх n>0. Звідси ННТ fHEMBED Equation.3= f1 .
Приклад 7. Знайдемо ННТ оператора ? : F1>F1, заданого умовою
EMBED Equation.3????
Оператор ? неперервний: (х, у)??(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, заданого умовою
EMBED Equation.3????
Оператор ? неперервний: (х, у)??(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 має вигляд
fН(x) = EMBED Equation.3
ВПРАВИ
1. Доведіть рекурсивність та знайдіть ННТ оператора ?: F1>F1, заданого наступною умовою:
1) EMBED Equation.3
2) EMBED Equation.3
3) EMBED Equation.3
4) EMBED Equation.3
5) EMBED Equation.3
2. Доведіть рекурсивність та знайдіть ННТ оператора ?: F2>F2, заданого наступною умовою:
1) EMBED Equation.3
2) EMBED Equation.3
3) EMBED Equation.3
3. Доведіть рекурсивність та знайдіть ННТ оператора ?: F1>F1, заданого наступною умовою:
1) EMBED Equation.3????
2) EMBED Equation.3????
4. Сформулюйте та доведіть для випадку п-арних операторів відпо-відні узагальнення теорем 11.2.1 – 11.2.3.
5. Нехай ? та ? ? рекурсивні оператори F1?F1 > F1. Доведіть, що існує найменша пара функцій f, g така, що f=?(f, g) та g=?(f, g), причому функцїї f та g є ЧРФ.