1 misol. Quyidagilar yechuvchi algoritmlarga misol bo‘la oladi

(0,0), (1,0), (0,1), (2,0), (1,1), (0,2), (3,0), (2,1)

(1,2), (0,3), (4,0), (3,1), (2,2), (1,3), (0,4),...

ro‘yxatini hosil qilamiz. ■

2. 
   teorema. Rekursiv bo ‘Imagan effektiv rekursiv sanaluvchi natural sonlar to 'plami mavjud.
   

Isboti. Effektiv rekursiv sanaluvchi ixtiyoriy U natural sonlar to‘plami berilgan bo'lsin. U to'plamning rekursiv emasligini isbotlash uchun, Post teoremasiga (2- teorema) ko'ra, uning CU to'ldiruvchisi effektiv rekursiv sanaluvchi emasligini isbotlash yetarli.

М 0, М Х, М 7,... - hamma rekursiv sanaluvchi natural sonlar to‘plamlaridagi effektiv sanab chiqilgan to‘plamlar bo isin. Demak, har qanday n e N uchun M n to‘plamni tiklash mumkin.

Endi U to‘plamning hamma elementlarini sanab chiqadigan A algoritmni kiritaylik. Bu algoritm (m, n) raqamli qadamda m e Mn ni hisoblab chiqadi. Agar bu son n son bilan ustma-ust tushsa, bu holda A algoritm uni U to‘plamga kiritadi, ya’ni не U <-» ne Mn. Bundan ko‘rinib turibdiki, har qanday rekursiv sanaluvchi to‘plamdan CU to‘plam hech boimaganda bitta element bilan farq qiladi, chunki CU shunday n elementlardan iboratki, n M n. Shuning uchun ham CU rekursiv sanaluvchi to‘plam emas. Demak, Post teoremasiga asosan U rekursiv to‘plam boimaydi. ■