3.Компактни оператопи. Свойства .

Всяко тотално изображение Г: F_n -> F_r ще наричаме оператор. Двойката (n,r) определя типа на оператора Г. Втора забележителна особеност на изображението G е неговата компактност. Нека Г е оператор от тип (n,r). Ще казваме че Г е компактен ако при всеки избор на f от F_n и естествени числа х_1,..., х_r и у е изпълнене еквивалентноста Г(f)( х_1,..., х_r ) у точно тогава когато съществува крайна подф-ция h на f за която Г(h)( х_1,..., х_r) у. Друго свойство на оператора G е неговата ефективност. Ако аргумента F изчислима функция то G (F) е изчислима ф-ция. Ако е известна програма а за изчислението на F можем алгоритмично да конструираме програма б за преместването на G (F). Нека Г е оператор от тип (n,r). Казваме че Г е ефективен ако съществува рекурсивна ф-ция h такава че Г (v_a⁽ⁿ⁾ ) = v _h(a)^r при всеки избор на код на програмата а. Рекурсивни оператори ще наричаме тези оператори които са едновременно компактни и ефективни. Да разгледаме съвкупноста F_n на n-местните частични функции в множ. на естествените числа. нека f и g са елементи на F_{n .} Ще казваме че f } g ако функцията g е продължение на функцията ,. т.с. f(х_1,..., х_n ) у -> g (х_1,..., х_n ) у при всеки избор на естествените числа х_1,..., х_n и у. Нека Х } F_{n .} Ще казваме че g е горна граница на Х ако g мажорира всеки елемент нс Х, т.е " f (f Х-> f } g). Функцията g е точна горна граница на Х ако g е горна граница на Х и g се мажорира от всички горни граници на Х. Има подмнож. на F_n които не притежават горни граници. Нека f₀ } f₁ } } f_k } e монотомнно растяща редица от елементи на F_n и G={(yхy,y) | $k(yхy) y}. Тогава G е графика на ф-ция g която е точна горна граница на редицата { f_k } _kN. Една частична ф-ция от F_n ще наричаме крайна ако притежава крайна дефиниционна област. Всяка крайна ф-ция е изчислима. Нека f₀ } f₁ } } f_k } е монотонно растяща редица и h } U f_к. Тогава за някой член f_m на редицата h } f_m. Нека разгледаме оператора Г от тип (1,1) опеделен като Г(f)(х) {0, ако f е тотална

{1, ако f не е тотална

Да допуснем че Г е компактен. Нека f е тотална ф-ция. Тогава Г(f)(0)=0.Каквато и крайна подф-ция h на f да вземем ще имаме Г (h)(0)=1. Компактните оператори имат свойства близки до тези на непрекъснатите ф-ции в множ. на реалните числа. Следващото твърдение е аналог на факта че две ф-ции които са определени и непрекъснати за всяко реално число и съвпадат в/у множ. на рационалните числа, съвпадат навсякъде. Нека Г₁ и Г₂ са компактни оператори от тип (n,r). Да предположим че Г₁ (h)= Г₂(h). Тогава Г₁(f)= Г₂(f) за всяка частична ф-ция f F_n. Всеки компактен оператор Г е монотомен. Оператора Г от тип (n,r) се нарича (изброимо ) непрекъснат ако при всеки избор на монотонно растящата редица f₀ } f₁ } } f_k } от елементи на F_n Г(U f_к ) е точна горна граница на множ. {Г(f_к) | к N} в F_r. Всеки компактен оператор е непрекъснат. Нека Г е оператор от тип (n,n). Казваме че f е минимална неподвижна точка на Г ако Г(f)= f и всеки път когато g F_n и Г(g)= g имаме f } g. Нека Г е монотомен оператор от тип (n,n). Нека f е минималното решение на неравенството Г(Х) }Х, т.е. Г(f) } f и " g(Г(g) } g-> f } g). Тогава f е минимална неподвижна точка на Г.