| Головна » Статті » Математика | [ Додати статтю ] |
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 : FF →F та мінімізації M : FF→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) FA : х(F). ФО : Fп→F називається неперервним, якщо для всіх хNп, yN та fFп маємо (х, у)(f) f : (х, у)(). Легко довести, що кожний неперервний оператор є монотонним. 11.1. ОПЕРАТОРИ ПЕРЕЛІКУ. ЧАСТКОВО РЕКУРСИВНІ ТА РЕКУРСИВНІ ОПЕРАТОРИ Ефективність множинного оператора : 2N→2N означає можли-вість ефективно задати множину (A), якщо ефективно задається множина А. Ефективні множинні оператори називаються [10] операторами переліку (скорочено ОП). Для кожного zN оператор переліку z : 2N→2N задається співвідношенням z(A) ={x | u(Fu А C(x, u)Dz)}. Інакше кажучи, xz(A) u(Fu А C(x, u)Dz). Теорема 11.1.1. Кожний оператор переліку є неперервним та монотонним. Множина АN однозначна, якщо С -1(А)={(l(x), r(x))} є функціо-нальним відношенням. Зрозуміло, що A однозначнa (Сm+1)-1(A) є функціональним відношенням для кожного m1. Отже, множина A однозначнa m1 fFm : A=Сm+1(f). Тому для множини всіх однозначних множин можна ввести наступне позначення: CF ={С(f) | fF1}={Сm+1(f) | fFm}. Кожний функціональний оператор : 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 називається частково рекурсивним оператором (ЧРО), якщо існує zN таке, що для всіх fFm маємо: (f) В цьому випадку кажуть, що ОП z визначає ЧРО. Тотальний ЧРО назвемо рекурсивним оператором (РО). Інакше кажучи, ФО : Fm→Fn рекурсивний оператор, якщо існує zN таке: для всіх fFm (f)=(Сn+1)-1(z(Сm+1(f))) (df1) Дамо безпосереднє визначення РО, не використовуючи поняття оператора переліку. Вживатимемо скорочення для х1 , ..., хп. ФО : Fm→Fn рекурсивний оператор, якщо існує zN таке: для всіх fFm, ( , у)Nп+1 маємо ( , у)(f) и(f у= (и, )) (df2) Зрозуміло, що таке визначення РО еквівалентне наступному: існує ЧРФ така: для всіх fFm, ( , у)Nп+1 маємо ( , у)(f) и(f у=(и, )) (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)=ff та ()=f для кожної скінченної f. Тому якщо (х, у)(f), то не існує скінченної функції f такої, що (х, у)(), бо ()=f. Отже, не є неперервним. Для доведення рекурсивності операторів корисним є наступний критерій рекурсивності: Теорема 11.1.4. Оператор : Fт→Fп є рекурсивним оператором неперервний та функція є ЧРФ. Розглянемо приклади використання теореми 11.1.4. Приклад 3. Оператор : Fт→Fп задається умовою (f)=g для всіх fFт, де g фіксована ЧРФ. Тоді є РО. Оператор неперервний: умова ( , у)(f) ( , у)() виконується для довільної скінченної f , адже (f)=()=g. Функція (и, )= є ЧРФ за ТЧ. Приклад 4. Задамо оператор : F1→F1 таким співвідношенням: (f)(x)= f(f(x+2))+5x для всіх fF1. Тоді є РО.Оператор неперервний: (х, у)(f) (х, у)() виконується для кожної скінченної f такої, що x+2D та f(x+2)D. Тепер (и, х) = є ЧРФ за ТЧ. Приклад 5. Оператор мінімізації М: Fп+1→Fп задається умовою М(f)( ) = у(f( , у)=0) для всіх fFп+1. Тоді М є РО. Оператор М неперервний: у=у(f( , у)=0) у=у(( , у)=0) виконується для кожної f такої, що ( , 0), ( , 1), ..., ( , у)D ; тому y=М(f)( ) y=М()( ) для кожної такої f. Тепер функція (и, ) = є ЧРФ за ТЧ. Приклад 6. Нехай ФО 0 : F1→F1 задається співвідношенням 0({(0,0)})={(0,0)} та 0({(1,0)})={(0,1)}; для інших fF1 значення 0(f) невизначене. Тоді 0 розширюється до ЧРО та не розширюється до жодного РО. Позаяк {C(0,0)}={0}=F1 та {C(1,0)}={2}=F4 , беремо z таке, що Dz ={C(0,20), C(1,22)}. Нехай ОП z задається таким Dz , тобто xz(A) u(FuА(x, u)Dz). Зрозуміло, що для кожних A 2N z(A) l(Dz)={0,1}. Маємо: Для ЧРО , який визначається таким ОП z , маємо: 1) Якщо (0,0)f та (1,0)f, то 0C(f) та 2C(f), звідки z(C(f))=. Отже, для таких f (f)=f . 2) Якщо (0,0)f та (1,0)f, то 0C(f) та 2C(f), звідки z(C(f))={0}=C(0,0). Отже, для таких f (f)={(0,0)}; 3) Якщо (0,0)f та (1,0)f, то 0C(f) та 2C(f), звідки z(C(f))={1}=C(0,1). Отже, для таких f (f)={(0,1)}; 4) Якщо (0,0)f та (1,0)f, то 0C(f) та 2C(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 немонотонний, тому не РО. 9. Сформулюйте визначення п-арного неперервного функціональ-ного оператора вигляду : F ... F ...F →Fп. 10. Сформулюйте визначення п-арного оператора переліку, п-арного ЧРО, п-арного РО та п-арного ЗРО. 11. Сформулюйте та доведіть для випадку п-арних операторів відпо-відні узагальнення теорем 11.1.1 – 11.1.5. 12. Доведіть рекурсивність операторів примітивної рекурсії R та суперпозиції Sn+1. 11.2. ТЕОРЕМА МАЙХІЛЛА-ШЕПЕРДСОНА. ТЕОРЕМИ ПРО НЕРУХОМУ ТОЧКУ Кожний ОП при обмеженні на РПМ задає на їх індексах ефективну операцію, тобто рекурсивну функцію. Теорема 11.2.1. Існує РФ s така, що для всіх z, yN маємо z(Dy)=Ds(x,y).. Наслідок. Нехай А є РПМ. Тоді z(A) є РПМ. Кожний РО при обмеженні на ЧРФ задає на їх індексах ефективну операцію, тобто рекурсивну функцію. Теорема 11.2.2 (Майхілл, Шепердсон). Для кожного РО : Fт→Fп існує РФ h така: для кожного kN маємо ( )= Наслідок. Нехай є РО, f є ЧРФ. Тоді (f) є ЧРФ. Функція h m-n-екстенсійна, якщо з умови випливає . 1-1-екстенсійні функції назвемо просто екстенсійними. Приклад 1. РФ h із теореми 11.2.2 m-n екстенсійна. Справді, з умови випливає . Теорема 11.2.3 (Майхілл, Шепердсон). Для кожної m-n-екстенсій-ної РФ h існує єдиний РО : Fт→Fп такий, що ( )= ). для кожного kN. Множина А називається найменшою нерухомою точкою (ННТ) оператора : 2N→2N , якщо: 1) (A)=A, тобто A нерухома точка (НТ) оператора ; 2) якщо (B)=B, то AB; тобто A найменша НТ оператора. Теорема 11.2.4 (С.Кліні). 1) Кожний неперервний множинний оператор : 2N→2N має найменшу нерухому точку; 2) якщо є оператором переліку, то його ННТ є РПМ. Множину A, що є ННТ оператора будуємо методом послідовних наближень. Задамо послідовність множин {An}nN так: A0=; An+1=An) для n0. Покладемо . Враховуючи неперервність, доводимо, що А є ННТ оператора Якщо є оператором переліку, то доводиться, що 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}nN так: f0=f; fn+1=(fn) для n0. Покладемо . Враховуючи неперервність, доводимо, що f є ННТ оператора . Якщо є рекурсивним оператором, то доводиться, що f є ЧРФ. | |
| Переглядів: 585 | |
| Всього коментарів: 0 | |