Ma’ruza 3: universal funktsiyalar. Ku’ZG’almas nuqtalar. Klini va rays teoremalari rekursiv va rekursiv sanaluvchi to`plamlar reja

Rekursiv va rekursiv sanaluvchi to`plamlar va ularning xossalari

naturalsonlarto`plami N={0,1,2,…..n,…}ning qism to`plami bo`lsin.

1-ta’rif .

funksiya to`plamning harakteristik funksiyasi deyiladi.

Ushbu tarifdan to`plamning harakteristik funksiyasi hamma yerda aniqlangan funksiya ekanligini ko`ramiz.

2-ta’rif .Harakteristik funksiyasi umumrekursiv bo`lgan to`plam rekursiv to`plam deyiladi.

Xususan harakteristik funksiyasi primitiv rekursiv bo`lgan to`plam primitiv rekursiv to`plam deyiladi.

1-misol.

,,lar rekursiv to`plamlardir. Ularning harakteristik funksiyalari mos ravishda







1-teorema. Agarva lar rekursiv to`plamlar u holda lar ham rekursiv to`plamlardir.

Isbot:,mos ravishda larning harakteristik funksiyalari bo`lsin.



lar mos ravishda larning harakteristik funksiyasi bo`ladi.Bundan ko`rinib turibdiki lar primitiv rekursiv funksiyadir.

Rekursiv to`plamlar algoritmlar nazariyasida asosiy ro`llardan birini o`ynaydi.natural sonning to`plamga kirishi yoki kirmasligi chekli qadamda ko`rsatib beradigan, ya’ni to`plamning harakteristik funksiyasi qiymatlarini hisoblaydigan algaritmni topish kerak. Bu to`plamga ,,kirish muammosi” deyilib, bunday algaritmlarning mavjud bo`lishi to`plamning haraktetistik funksiyasining umumrekursiv bo`lishiga teng kuchlidir. Shuning uchun rekursiv to`plamlarni ,,kirish muammosi” algaritmik yechiluvchi to`plamlar deb qarash mumkin.

3-ta’rif. Bo`sh yoki biror umumrekursiv funksiya qiymatlarini to`plamidan iborat bo`lgan to`plam rekursiv sanab chiqiluvchi to`plam deyiladi. O`znavbatida mazkur funksiya to`plamni sanab chiquvchi funksiyasi deyiladi.