 |
 |
Реферат на тему:
Eфективні операції на функціях та множинах
Множину всіх n-арних функцій на N, тобто функцiй iз Nп в N, позначимо Fп. Об'єднання множин Fп для всіх п(1 позначимо F. Множину всіх тотальних функцій із Fп та множину всіх тотальних функцій із F відповідно позначимо Tп та T . Cкінченні множини в цьому розділі позначаємо F, скінченні функції позначаємо (.
Довільну функцію вигляду (: (2N)m\x21922N назвемо m-арним множинним оператором (скорочено МО).
Довільну функцію вигляду \x03A8: (F)m\x2192F назвемо m-арним функціональним оператором (скорочено ФО).
Функціональні оператори називають також операціями на функціях, або композиціями.
Приклад. Операції суперпозиції Sn+1 : (F)m\x2192F, примітивної рекурсії R : F(F \x2192F та мінімізації M : F(F\x2192F є прикладами ФО.
МО (: (2N)m\x21922N називається монотонним, якщо із умови А1(В1 , А2 (В2 , ..., Ат (Вт випливає ((А1 , ..., Ап) (((В1 , ..., Вп).
ФО (: (F)m\x2192F називається монотонним, якщо із умови f1 (g1 , f2 (g2 , ..., fт (gт випливає ((f1 , ..., fп) (((g1 , ..., gп).
МО (: (2N)m\x21922N називається неперервним, якщо для всіх х(N, A((2N)m маємо х(((A) ( ( F(A : х(((F).
ФО (: Fп\x2192F називається неперервним, якщо для всіх х(Nп, y(N та f(Fп маємо (х, у)(((f) ( (( (f : (х, у)(((().
Легко довести, що кожний неперервний оператор є монотонним.
11.1. ОПЕРАТОРИ ПЕРЕЛІКУ. ЧАСТКОВО РЕКУРСИВНІ ТА РЕКУРСИВНІ ОПЕРАТОРИ
Ефективність множинного оператора (: 2N\x21922N означає можли-вість ефективно задати множину ((A), якщо ефективно задається множина А. Ефективні множинні оператори називаються [10] операторами переліку (скорочено ОП).
Для кожного z(N оператор переліку (z : 2N\x21922N задається співвідношенням (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\x2192Fn задає множинний оператор (: CF\x2192CF та навпаки:
( : Fm \x2192 Fn
Сm+1(((Сm+1)-1 Сn+1(((Сn+1)-1
( : CF \x2192 CF
Звідси ((f)=(Сn+1)-1(((Сm+1(f))) та ((A)=Сn+1((((Сm+1)-1(A))).
ФО (: Fm\x2192Fn називається частково рекурсивним оператором (ЧРО), якщо існує z(N таке, що для всіх f(Fm маємо:
В цьому випадку кажуть, що ОП (z визначає ЧРО (.
Тотальний ЧРО назвемо рекурсивним оператором (РО).
Інакше кажучи, ФО (: Fm\x2192Fn \xF02D\xF020рекурсивний оператор, якщо
існує z(N таке: для всіх f(Fm ((f)=(Сn+1)-1((z(Сm+1(f))) (df1)
для х1 , ..., хп.
ФО (: Fm\x2192Fn \xF02D\xF020рекурсивний оператор, якщо
, у)(Nп+1 маємо
)) (df2)
Зрозуміло, що таке визначення РО еквівалентне наступному:
, у)(Nп+1 маємо
)) (df3)
Теорема 11.1.2. Визначення df1, df2 та df3 еквівалентні.
Надалі для РО будемо, як правило, використовувати df3.
Теорема 11.1.3. Кожний РО є неперервним та монотонним.
Приклад 1. Нехай оператор (: F1\x2192F1 задається співвідношеням
Тоді ( немонотонний, отже, не РО.
Візьмемо скінченну ((f( та нескінченну f((. Тоді ((()=((f( та ((f)=f( . Маємо f(( та ((f)((((). Отже, ( не є монотонним.
Приклад 2. Нехай оператор (: F1\x2192F1 задається співвідношеням
\xF020 Тоді ( не неперервний і не РО.
Візьмемо функцію f із нескінченною Еf (наприклад, f \xF02D тотожна функція). Тоді ((f)=f(f( та ((()=f( для кожної скінченної ((f. Тому якщо (х, у)(((f), то не існує скінченної функції ((f такої, що (х, у)((((), бо ((()=f( =(. Отже, ( не є неперервним.
Для доведення рекурсивності операторів корисним є наступний критерій рекурсивності:
Теорема 11.1.4. Оператор (: Fт\x2192Fп є рекурсивним оператором ( ( неперервний та функція
є ЧРФ.
Розглянемо приклади використання теореми 11.1.4.
Приклад 3. Оператор (: Fт\x2192Fп задається умовою ((f)=g для всіх f(Fт, де g \xF02D\xF020фіксована ЧРФ. Тоді ( є РО.
є ЧРФ за ТЧ.
Приклад 4. Задамо оператор (: F1\x2192F1 таким співвідношенням: ((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\x2192F1 задається співвідношенням (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}. Маємо:
\xF02D якщо ((А та ((А, то (z(A)={0,1};
\xF02D\xF020якщо ((А та ((А, то (z(A)={0};
\xF02D якщо ((А та ((А, то (z(A)={1};
\xF02D якщо 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} \xF02D неоднозначна множина. Отже, для таких 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т\x2192Fп такий, що Tт(D( . Тоді ( є РО.
Наслідок. Для класів ЗРО, РО та ЧРО маємо строгі включення ЗРО(РО(ЧРО.
За теоремою 11.1.5 ЗРО(РО. Але РО прикладу 3 не є, очевидно, ЗРО, якщо ЧРФ g взяти нетотальною, тобто не РФ. За визначенням РО(ЧРО. Але ЧРО ( із прикладу 6 немонотонний, тому не РО.
ВПРАВИ
1. Нехай (z \xF02D оператор переліку. Дослідити співвідношення:
1) між множинами (z(А(В) та (z(А)((z(В);
2) між множинами (z(А(В) та (z(А)((z(В).
теж монотонний
теж неперервний
теж рекурсивний
5. Доведіть рекурсивність оператора ( : F1\x2192F1, заданого умовою:
.
6. Доведіть рекурсивність оператора ( : F1\x2192F1, заданого так:
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\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) якщо ( є оператором переліку, то його ННТ є РПМ.
.
Враховуючи неперервність, доводимо, що А є ННТ оператора (. Якщо ( є оператором переліку, то доводиться, що A є РПМ.
Функція f називається найменшою нерухомою точкою оператора (: Fп\x2192Fп, якщо:
1) ((f)=f, тобто f \xF02D нерухома точка оператора ( ;
2) якщо ((g)=g, то f (g; тобто f \xF02D найменша НТ оператора (.
Приклад 2. Нехай ННТ f оператора ( є тотальною функцією. Тоді f \xF02D єдина нерухома точка оператора (.
Приклад 3. Найменша нерухома точка тотожного оператора \xF02D\xF020це f(. Тотожний оператор є ЗРО. Отже, для ЗРО найменша нерухома точка може бути нетотальною функцією.
Теорема 11.2.5 (С.Кліні). 1) Кожний неперервний ФО (: Fп\x2192Fп має найменшу нерухому точку;
2) якщо ( є РО, то його ННТ є ЧРФ.
.
Враховуючи неперервність, доводимо, що f є ННТ оператора (. Якщо ( є рекурсивним оператором, то доводиться, що f є ЧРФ.
Нехай РО (: F1\x2192F1 визначений ОП (z : для всіх f(F1 маємо ((f)=С-1((z (С(f))). Нехай А є НТ оператора (z : А=(z (А). Тоді функція f =С-1(А) є нерухомою точкою РО (: ((f)=С-1((z (С(f)))= =С-1((z (А))=С-1(А)=f . З іншого боку, нехай f \xF02D НТ РО (: ((f)=f. Тоді множина А=С(f) \xF02D НТ оператора (z : (z (С(f))=С(((f))=С(f).
Приклад 4. Для ЧРО не РО ( найменшої нерухомої точки може не існувати. Це буває тоді, коли множина А, що є \xF020ННТ відповідного ОП (z , \xF020неоднозначна. Тоді кожна В(А неоднозначна, тому такий ( взагалі не має нерухомих точок.
Приклад 5. Знайдемо ННТ оператора ( : F1\x2192F1, заданого умовою
Оператор ( неперервний: (х, у)(((f) ( (х, у)(((() виконується при х=0 для довільної скінченної ((f, при х>0 ця умова викону-ється для кожної скінченної ((f такої, що x+1(D( . Отже, ( має ННТ fH , яку знайдемо методом послідовних наближень.
Маємо f0=f(. Тепер знаходимо f1 та f2:
Приклад 6. Знайдемо ННТ оператора ( : F2\x2192F2, заданого умовою
\xF02E\xF020\xF020\xF020
Оператор ( неперервний: умова (х, у, z)(((f) ( (х, у, z)(((() виконується при х=0 для довільної скінченної ((f, при х>0 ця умова виконується для кожної скінченної ((f такої, що (х, у)(D( та (х\xF02D1, f(х, у))(D( . Отже, ( має ННТ fH , яку знайдемо методом послідовних наближень. Маємо f0=f(. Тепер знаходимо f1 та f2:
бо f1(х, у) невизначене при x>0.
= f1 .
Приклад 7. Знайдемо ННТ оператора ( : F1\x2192F1, заданого умовою
\xF02E\xF020\xF020\xF020
Оператор ( неперервний: (х, у)(((f) ( (х, у)(((() виконується при х=0 для довільної скінченної ((f, при х>0 умова виконується для кожної скінченної ((f такої, що x\xF02D1(D( . Отже, ( має ННТ.
Метод послідовних наближень тут вимагає нескінченної кількості кроків, бо fп+1 ( fп для всіх n(0. Тому використаємо обхідні шляхи. Нехай fH \xF02D ННТ нашого оператора. Тоді для кожного х(N маємо fН(х)=((fН)(х) = 2х\xF02D1+ fН(х\xF02D1) = 2х\xF02D1+((fН)(х\xF02D1) = 2х\xF02D1+2х\xF02D3+fН(х\xF02D2) = … = 2х\xF02D1+2х\xF02D3+ … +1+fН(0) = 2х\xF02D1+2х\xF02D3+ … +1+0 = х2. Отже, для всіх х(N fН(х) = х2. Тому така fH \xF02D єдина нерухома точка нашого (.
Приклад 8. Знайдемо ННТ оператора ( : F1\x2192F1, заданого умовою
\xF02E\xF020\xF020\xF020
Оператор ( неперервний: (х, у)(((f) ( (х, у)(((() виконується при х>55 для довільної скінченної ((f, при х(55 умова викону-ється для кожної скінченної ((f такої, що x+7(D( та f(x+7)(D( . Отже, ( має ННТ, нехай це функція fH . Для кожного х>55 маємо fН(x)=((fН)(х) = х\xF02D6. Тепер 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 \xF02D єдина нерухома точка оператора (, причому така fH має вигляд
ВПРАВИ
1. Доведіть рекурсивність та знайдіть ННТ оператора (: F1\x2192F1, заданого наступною умовою:
2. Доведіть рекурсивність та знайдіть ННТ оператора (: F2\x2192F2, заданого наступною умовою:
3. Доведіть рекурсивність та знайдіть ННТ оператора (: F1\x2192F1, заданого наступною умовою:
\xF02E\xF020\xF020\xF020
\xF02E\xF020\xF020\xF020
4. Сформулюйте та доведіть для випадку п-арних операторів відпо-відні узагальнення теорем 11.2.1 – 11.2.3.
5. Нехай ( та ( \xF02D рекурсивні оператори F1(F1 \x2192 F1. Доведіть, що існує найменша пара функцій f, g така, що f=((f, g) та g=((f, g), причому функцїї f та g є ЧРФ.
|
|
|
 |
|
