Mavzu: rekursiv va rekursiv sanaluvchi to‘plamlar. Bajardi: Ro`ziyeva M

Qismiy rekursiv va um um rekursiv funksiyalar. 8- t a ’rif. Agar /(x , ,x 2 ,...,x n) funksiyani boshlang'ich funksiyalardan superpozitsiya, prim itiv rekursiya sxemasi va minimallash operatori ( /I -operatori) amallarini chekli son marta qo ‘Hash natijasida hosil etish mumkin b o ‘Isa, и holda / ( x p x,,...,xn) qismiy rekursiv (rekursiv) funksiya deb ataladi. 8- ta’rif 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 prim itiv rekursiv funksiya о ‘z navbatida qismiy rekursiv funksiya bo ‘ladi. 9- ta’rif. Agar / ( x , , x 2,...,x n) funksiya qismiy rekursiv va argumentlarning barcha qiymatlarida aniqlangan bo ‘Isa, и holda f (x ,, x 2,..., x n) 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 Chyorch tezisi deb ataluvchi quyidagi tezis o'rganilgan edi. Har qanday intuitiv hisoblanuvchi funksiya qismiy rekursiv funksiya bo 'ladi.

Qismiy rekursiv va um um rekursiv funksiyalar. 8- t a ’rif. Agar /(x , ,x 2 ,...,x n) funksiyani boshlang'ich funksiyalardan superpozitsiya, prim itiv rekursiya sxemasi va minimallash operatori ( /I -operatori) amallarini chekli son marta qo ‘Hash natijasida hosil etish mumkin b o ‘Isa, и holda / ( x p x,,...,xn) qismiy rekursiv (rekursiv) funksiya deb ataladi. 8- ta’rif 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 prim itiv rekursiv funksiya о ‘z navbatida qismiy rekursiv funksiya bo ‘ladi. 9- ta’rif. Agar / ( x , , x 2,...,x n) funksiya qismiy rekursiv va argumentlarning barcha qiymatlarida aniqlangan bo ‘Isa, и holda f (x ,, x 2,..., x n) 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 Chyorch tezisi deb ataluvchi quyidagi tezis o'rganilgan edi. Har qanday intuitiv hisoblanuvchi funksiya qismiy rekursiv funksiya bo 'ladi.