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

3-teorema. (Post).rekursiv to`plam bo`lishi uchun ning o`zi va to`ldiruvchisi ham rekursiv sanaluvchi bo`lishi zarur va yetarli.

Isbot. Zarurligi: 2-teoremaga ko`ra rekursiv to`plam bo`lsa rekursiv sanab chiqiluvchi to`plam bo`ladi. 1-teoremaga ko`ra esa ham rekursiv to`plam va demak rekursiv sanaluvchi to`plam bo`ladi.

Yetarliligi:lar rekursiv sanaluvchi to`plamlar bo`lsin. bo`lsa yetarliligi ravshandir. Agar bo`lsa u holda to`plamlar mos ravishda qandaydir umumrekursiv funksiyalar qiymatlari to`plamidan iborat bo`ladi.

Ushbu algaritmik jarayonni qaraylik.

natural son bo`lsa, u to`plamga kiradimi yoki ga kiradimi degan masalani hal etish uchun sonlarni ketma-ket qarab chiqamiz.

Agar funksiyaning qiymati bo`lsa, u holda agarfunksiyaning qiymati bo`lsa bo`lib, bo`lgani uchun albatta ning qiymatlaridan iborat bo`ladi. Boshqacha aytganda to`plamning harakteristik funksiyasi to`liq aniqlangan umumrekursiv funksiya, ning o`zi esa rekursiv to`plam bo`ladi.

4-ta’rif. Shunday umumrekursiv funksiya mavjud bo`lsaki, to`plam ning qiymatlar to`plamidan iborat bo`lib o`suvchi funksiya bo`lsa u holda o`sib borish tartibida rekursiv sanaluvchi to`plam deyiladi.

4-misol. 1,3,5,7,9,… toq sonlar to`plami o`sib borish tartibida rekursiv sanaluvchi to`plamlardir. o`suvchi umumrekursiv funksiyaning qiymatlari to`plamidan iboratdir.