Головна » Статті » Математика [ Додати статтю ]

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] операторами переліку (скорочено ОП).

Для кожного zN оператор переліку 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 таке: для всіх fFm (f)=(Сn+1)-1(z(Сm+1(f))) (df1)

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

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

існує zN таке: для всіх fFm, ( , у)Nп+1 маємо

( , у)(f) и(f у= (и, )) (df2)

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

існує ЧРФ така: для всіх fFm, ( , у)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 для всіх fF1. Тоді є РО.Оператор неперервний: (х, у)(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)}; для інших 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 , тобто 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, yN маємо 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}nN так: A0=; An+1=An) для n0. Покладемо .

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

Враховуючи неперервність, доводимо, що f є ННТ оператора . Якщо є рекурсивним оператором, то доводиться, що f є ЧРФ.
Категорія: Математика | Додав: КрАсАв4іК (22.01.2013)
Переглядів: 209 | Рейтинг: 0.0/0
Всього коментарів: 0
Додавати коментарі можуть лише зареєстровані користувачі.
[ Реєстрація | Вхід ]