Eфективні операції на функціях та множинах, Детальна інформація

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