1. Rekursiv, rekursiv sanaluvchi to‘plam tushunchalari. Rekursiv va rekursiv sanaluvchi to‘plamlar xossalari. Post teoremasi

1-misol. natural sonlar kvadratlari to‘plami effektiv rekursiv sanaluvchi to‘plam bo‘lishi yoki bo‘lmasligini aniqlaymiz.
to‘plam effektiv rekursiv sanaluvchi to‘plam bo‘ladi, chunki uning elementlarini hosil qilish uchun ketma-ket natural sonlarni olib, ularni kvadratga ko‘tarish kerak. Bu to‘plam ham rekursiv bo‘ladi. Haqiqatan ham, birorta natural sonning to‘plamga kirish yoki kirmasligini aniqlash uchun uni tub ko‘paytuvchilarga ajratish kerak. Bu usul natural son biror natural sonning kvadratimi yoki yo‘qmi degan savolga javob topish imkonini beradi. ■
2-misol. Tartiblangan natural sonlar juftliklaridan iborat to‘plam effektiv rekursiv sanaluvchi ekanligini isbotlaymiz.
Tartiblangan natural sonlar juftliklaridan iborat to‘plamning effektiv rekursiv sanaluvchi ekanligini isbotlash uchun diagonal metodi deb aytiluvchi usuldan foydalanamiz. Buning uchun hamma tartiblangan natural sonlar juftliklarini 1-shakldagi ko‘rinishda yozamiz.
Yuqori chap burchakdan boshlab ketma-ket 1-shaklda ko‘rsatilgan yo‘nalishlar bo‘yicha o‘tib to‘plam elementlarini sanab chiqamiz. U holda bu juftliklarning


ro‘yxatini hosil qilamiz. ■
3-teorema. Rekursiv bo‘lmagan effektiv rekursiv sanaluvchi natural sonlar to‘plami mavjud.
Isboti. Effektiv rekursiv sanaluvchi ixtiyoriy natural sonlar to‘plami berilgan bo‘lsin. to‘plamning rekursiv emasligini isbotlash uchun, Post teoremasiga (2-teorema) ko‘ra, uning to‘ldiruvchisi effektiv rekursiv sanaluvchi emasligini isbotlash yetarli.

– hamma rekursiv sanaluvchi natural sonlar to‘plamlaridagi effektiv sanab chiqilgan to‘plamlar bo‘lsin. Demak, har qanday uchun to‘plamni tiklash mumkin.
Endi to‘plamning hamma elementlarini sanab chiqadigan algoritmni kiritaylik. Bu algoritm raqamli qadamda ni hisoblab chiqadi. Agar bu son son bilan ustma-ust tushsa, bu holda algoritm uni to‘plamga kiritadi, ya’ni .
Bundan ko‘rinib turibdiki, har qanday rekursiv sanaluvchi to‘plamdan to‘plam hech bo‘lmaganda bitta element bilan farq qiladi, chunki shunday elementlardan iboratki, . Shuning uchun ham rekursiv sanaluvchi to‘plam emas. Demak, Post teoremasiga asosan rekursiv to‘plam bo‘lmaydi. ■
Izoh. Isbot qilingan bu teorema aslida Gyodelning formal arifmetika to‘liqsizligi haqidagi teoremasini oshkormas tarzda qamrab olgan.