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

2-teorema.Agar rekursiv to`plam bo`lsa u holda u rekursiv sanaluvchi to`plam bo`ladi.

Isbot. Mumkin bo`lgan 3ta holni qaraymiz.

a) bo`lsa teorema o`rinli ekani ma’lum

b) chekli to`plam bo`lsin. U holda bu to`plamni sanab chiquvchi funksiya

bo`ladi.

v)cheksiz to`plam ning harakteristik funksiyasi bo`lsin, u holda

yordamida aniqlangan funksiya to`plamning sanab chiquvchi funksiyasidir.

2-misol.



-rekursiv sanaluvchi to`plam lekin rekursiv to`plam emas.
3-misol.

-rekursiv sanaluvchi to`plam emas.