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

1- natija. No I funksiya 0 (x) primitiv rekursiv funksiyadir

2- n a ti ja . Agar к biror birtun musbat son bo ‘Isa, и holda c ; ( x ,, x 2 x n ) = к о ‘zgarmas funksiya primitiv rekursiv funksiyadir. 3 - natija. Superpozitsiya amalini har bir f\ funksiya x],x,,...jcn о ‘zgaruvchilarning faqat ayrimlaridangina bog'liq ho ‘Iganda ham ishlatish mumkin. Xuddi shunday prim itiv rekursiya sxemasida ham ф funksiya Xl ,X 2, . . . , X n о ‘zgaruvchilarning ayrimlariga bog'liq bo'lmasligi mumkin va Ц/ funksiya f ( y , x 2, x J,...,xn) funksiyaga, hamda shuningdek x i , x 2,...,xn, y о ‘zgamvchilarning ayrimlariga bog'liq bo'lmasligi mumkin. Shunday qilib, har bir primitiv rekursiv funksiya qismiy rekursiv (rekursiv) funksiya bo'lgani uchun, qismiy rekursiv funksiyalar sinfi primitiv rekursiv funksiyalar sinfidan kengdir. Qismiy rekursiv funksiya tushunchasi algoritmlar nazariyasining asosiy tushunchalaridan biridir. Shuni ham ta’kidlab o'tamizki, birinchidan, har qanday qismiy rekursiv funksiyaning qiymati mexanik xarakterga ega bo‘lgan ma’lum bir protsedura yordamida hisoblanadi

• 
  2- n a ti ja . Agar к biror birtun musbat son bo ‘Isa, и holda c ; ( x ,, x 2 x n ) = к о ‘zgarmas funksiya primitiv rekursiv funksiyadir. 3 - natija. Superpozitsiya amalini har bir f\ funksiya x],x,,...jcn о ‘zgaruvchilarning faqat ayrimlaridangina bog'liq ho ‘Iganda ham ishlatish mumkin. Xuddi shunday prim itiv rekursiya sxemasida ham ф funksiya Xl ,X 2, . . . , X n о ‘zgaruvchilarning ayrimlariga bog'liq bo'lmasligi mumkin va Ц/ funksiya f ( y , x 2, x J,...,xn) funksiyaga, hamda shuningdek x i , x 2,...,xn, y о ‘zgamvchilarning ayrimlariga bog'liq bo'lmasligi mumkin. Shunday qilib, har bir primitiv rekursiv funksiya qismiy rekursiv (rekursiv) funksiya bo'lgani uchun, qismiy rekursiv funksiyalar sinfi primitiv rekursiv funksiyalar sinfidan kengdir. Qismiy rekursiv funksiya tushunchasi algoritmlar nazariyasining asosiy tushunchalaridan biridir. Shuni ham ta’kidlab o'tamizki, birinchidan, har qanday qismiy rekursiv funksiyaning qiymati mexanik xarakterga ega bo‘lgan ma’lum bir protsedura yordamida hisoblanadi