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

Ma’ruza 3:
UNIVERSAL FUNKTSIYALAR. KU’ZG’ALMAS NUQTALAR. KLINI VA RAYS TEOREMALARI
REKURSIV VA REKURSIV SANALUVCHI TO`PLAMLAR
Reja:

1. 
   Universal funksiyalar.
   
2. 
   Ku’zg’almas nuqtalar.
   
3. 
   Klini va Rays teoremalari
   
4. 
   Rekursiv to`plamlar.
   
5. 
   Rekursiv sanaluvchi to`plamlar.
   
6. 
   Post teoremasi.
   

Avval Klini teoremasidan boshlaymiz.

Teorema 1 (Klini). Agar f – umumrekursiv funksia bu’lsa shunday n mavjudki

φ_n= φ_f(n) .

Isbot. Qu’yidagi funksiyani ta’riflaymiz:

ψ-ni hisoblaydigan instruktsiyalar u-dan bir usulli beriladi, demak ψ-ni har biu uchun umumrekursiv funksiya, aytaylik g, hisoblaydi. Ya’ni

φ_g(u)= ψ.

Demak,

Endi f – ihtiyoriy umumrekursiv funksiya, bu holda superpozitsiya fg ham umumrekursiv vas hu funksiyani birorta nomerini belgilaylik. Masalan v deylik, fg = φ_v . Ravshanki, φ_v(v) aniqlangan. Bundan kelib chiqadi

va n=g(v) f uchun ku’zg’almas nuqta bu’ladi. Isbot tugadi