1 misol. Quyidagilar yechuvchi algoritmlarga misol bo‘la oladi

Qismiy rekursiv va umumrekursiv funksiyalar.

6- ta’rif. Agar /(x , ,x 2 ,...,xn) funksiyani boshlang'ich funk- siyalardan superpozitsiya, primitiv rekursiya sxemasi va minimallash operatori ( /I -operatori) amallarini chekli son marta qo ‘Hash natijasida hosil etish mumkin bo‘Isa, и holda /(x px,,...,xn) qismiy rekursiv (rekursiv) funksiya deb ataladi.

Primitiv rekursiv funksiyaning ta’rifidan faqat boshlang'ich funksiyalarga qo'shimcha ravishda fl -operatorini qo'llashga ruxsat berilishi bilan farq qiladi. Shuning uchun ham har qanday primitiv rekursiv funksiya о ‘z navbatida qismiy rekursiv funksiya bo ‘ladi.

7- ta’rif. Agar /( x ,,x 2,...,xn) funksiya qismiy rekursiv va argumentlarning barcha qiymatlarida aniqlangan bo ‘Isa, и holda f (x,, x2,..., xn) umumrekursiv funksiya deb ataladi.

Ushbu A(x), 0(x), I'”(x), /(v,x) = v + x, f(y,x)-x-y va / (y,x) = x n funksiyalar umumrekursiv funksiyalardir. Ushbu bobning 3- paragrafida C h y o r c h t ez i s i deb ataluvchi quyidagi tezis o'rganilgan edi. Har qanday intuitiv hisoblanuvchi funksiya qismiy rekursiv funksiya bo 'ladi. Bu tezisni isbotlash mumkin emasligi yuqorida aniqlangan edi. Chunki u intuitiv hisoblanuvchi funksiya noqat’iy matematik tushunchasini qat’iy aniqlangan qismiy rekursiv funksiya matematik tushunchasi bilan bog'laydi. Ammo, agar shunday intuitiv hisoblanuvchi funsiya tuzish mumkin bo'lsaki, u o'z navbatida qismiy rekursiv funksiya bo'lmasa, u holda bu tezisni rad etish mumkin. Lekin, bunday holning mavjudligini hozirgacha hech kim ko'rsata olmagan.

Teorema. g (y |,j’2,...,jt ) primitiv rekursiv (qismiy rekursiv) funksiya va x,,x2 xn har xil o ‘zgaruvchilar bo'lsin. Agar har bir I (1 < г < к) uchun z t o'zgaruvchi xl,x2,—,xn о ‘zgaruvchilarning biri bo'lsa, и holda / (x,,x2,...,xn) = g ( z l, z 2,...,zk) funksiya ham primitiv rekursiv (qismiy rekursiv) funksiya bo ‘ladi.

I s b о t i. zi = xJj (1 < j i < n) bo‘lsin. U holda z; =/"(x i,x2,...,x„) va y/(xl,x2,. ..,хл) = ф (/''(х ,,х 2, . . . , х „ Г ‘к(х],х2,...,хп)) bo‘ladi. Shunday qilib, у/ funksiyani ф , I" ,...,I” funksiyalardan superpozitsiya amali orqali hosil qilish mumkin, ya’ni Ц/ primitiv rekursiv (rekursiv) funksiya bo‘ladi.

Bu teorema soxta o‘zgaruvchilami kiritish, о‘zgaruvchilarning o‘mini almashtirish va ulami aynan tenglashtirish jarayoni primitiv rekursiv va qismiy rekursiv funksiyalami o‘z sinflaridan chiqarmasligini bildiradi.