Hisoblanuvchi funksiyalar. Qismiy rekursiv va umumrekursiv funksiyalar. A. Chyorch tezisi

Hisoblanuvchi funksiyalar. Qismiy rekursiv va umumrekursiv funksiyalar. A.CHyorch tezisi

Reja
1. Rekursiv funsiyalar va ular ustida amallar.

2. Sodda funksiyalar va ular bilan ishlash.
3. S, R,M operatorlari.
4. A. Chyorch tezisi

1- ta’rif. Agar birorta funksiyaning aniqlanish sohasi ham, qiymatlar sohasi ham natural sonlar to ‘plamining qism to ‘plamlari bo ‘Isa, u holda bunday funksiya arifmetik (sonli) funksiya deb ataladi. Natural sonlar to'plamida berilgan har qanday munosabatlarga arifmetik munosabat deyiladi.

Masalan, natural sonlar to'plamida f(x,y) = x-y (ko‘paytma) - ikki argumentli arifmetik funksiyadir, x + y < z - uch argumentli arifmetik munosabat. Arifmetik funksiya va arifmetik munosabat tushunchalari intuitiv tushunchalardir va hech qanday formal sistema bilan bogMangan emas. Arifmetik (sonli) funksiyaning qiymatini hisoblovchi algoritm mavjudligini aniqlash algoritmik muammolardan biridir.

2. ta’rif. Agar g = f(xl,x2,...,xn) funksiyaning qiymatini hisoblovchi algoritm mavjud bo‘Isa, и holda и effektiv (samarali) hisoblanuvchifunksiya deb ataladi. Bu ta’rifda algoritm tushunchasi intuitiv ma’noda tushunilganligi sababli, effektiv hisoblanuvchi funksiya tushunchasi ham intuitiv tushuncha bo‘ladi. Ammo algoritm tushunchasidan effektiv hisoblanuvchi funksiya tushunchasiga o‘tishning o‘ziga xos ijobiy tomoni bor. Masalan, algoritm tushunchasiga qo‘yilgan hamma talablar (o'ziga xos xususiyatlari sifatida) rekursiv (qaytarish) funksiyalar majmuasi deb ataladigan hamma hisoblanuvchi funksiyalar majmuasi uchun bajariladi. Gyodel birinchi bo‘lib biror formal sistemada aniqlangan hamma sonli funksiyalar sinfini rekursiv funksiyalar sinfi sifatida ifodaladi. 1936-yilda Chyorch ham boshqa asoslarga suyanib rekursiv funksiyalar sinfini tasvirlagan edi. Bu yerda hisoblanuvchi funksiyalar sinfi quyidagicha tuziladi.

Sodda funksiyalar:
• O(x)=0 - no’l funksiyasi
• S(x)=x+1 ga oshirish funksiyasi
• (x1,…xm,xm+1,…xn)=xm tanlash funksiyasi

Operatorlar

Ta’rif.(x1,…,xn) funksiya ,, …, funksiyalardan superpozitsiya operatorini qo’llab olingan deyiladi agar
(x1,…,xn)=((x1,…,xn),, …(x1,…,xn)) kabi yozish
mumkin bo’lsa.( S operatori)
Ta’rif. (x1,…,xn,y) funksiya (x1,…,xn,y,z) funksiyalardan primitive rekursiv operatorini qo’llab olingan deyiladi agar uni
ko’rinishda qurish mumkin bo’lsa.(R operatori)
•
f(x,y) funksiya berilgan bo’lsin. Fikserlangan x uchun y ning qaysi qiynatida f(x,y)=0
f(x,y) funksiya berilgan bo’lsin. Fikserlangan x uchun y ning qaysi qiynatida f(x,y)=0
bo’lishini tushintiraylik. Boshqacha aytganda f(x,y) ing berilgan qiymati fikserlangan x uchun y ning
eng kichik qiymatini topish kerak. Ya’ni:
t(x)=My(f(x,y)=0) (f(x,y)=0 bo’ladigan eng kicik y kabi o’qiladi)
Ko’p o’zgaruvchili funksiya uchun ham xuddi shu usul bilan topiladi:
t(x1,…,xn)=My(f (x1,…,xn,y)=0) (M operatori)
Ta’rif. (x1,…,xn,y) funksiyadan t(x1,…,xn) funksiyaga o’tishga M operatorini qo’llash deyiladi.
t(x1,…,xn) funksiyani quyidagi algoritm bilan hisoblaymiz:
f(x1,…,xn ,0)=0 bo’lsa t(x1,…,xn)=0 bo’ladi. Aks holda -
f(x1,…,xn,1)=0 bo’lsa t(x1,…,xn)=1 bo’ladi. Aks holda -
……………
shu usul bilan topilgan t(x1,…,xn) funksiya f()=0 shartni qanoatlantiruvchi eng kichikfunksiyadir.
Misollar: 1. f(x)=x+3
f(x)=S(S(S(x)))=((x+1)+1)+1
2.f(x,y)=x+y- sum(x,y)
•
3 f(x,y)= x*y
3 f(x,y)= x*y
x*y=
4 f(x,y)=x-y
f(x,y)=Mz(y+z=x)=Mz(=). f(7,2) ni hisoblaylik
x=7, y=2
z=0, 2+0=7 noto’g’ri
z=1, 2+1=7 noto’g’ri
z=2, 2+2=7 noto’g’ri
z=3, 2+3=7 noto’g’ri
z=4, 2+4=7 noto’g’ri
z=5, 2+5=7 to’g’ri
demak f(7,2)=5 ekan.
•
Ta’rif: (x1,…,xn) funksiya qismiy rekursiv funksiya deyiladi agarda u sodda funksiyalardan S,R,M operatorlarni chekli marta qo’llashbilan olinishi mumkin bo’lsadi.
Chorch tezisi:
Har bir intuitive hisoblanuvchi funksiya qismiy rekursivdir.
Demak biz biladigan barcha siklik jarayonlarni rekursiya yordamid hisoblash mumkin ekan. (matematik asosi)
Masalan: f(n)=n! - ni qaraylik

Gyodel birinchi bo‘lib biror formal sistemada aniqlangan hamma sonli funksiyalar sinfini rekursiv funksiyalar sinfi sifatida ifodaladi. 1936-yilda Chyorch ham boshqa asoslarga suyanib rekursiv funksiyalar sinfini tasvirlagan edi. Bu yerda hisoblanuvchi funksiyalar sinfi quyidagicha tuziladi. 3- ta’rif. Quyidagi sonli funksiyalar boshlang‘ich {oddiy, bazis) funksiyalar deyiladi: 1) nol funksiya (bekor qilish operatori): har bir x uchun 0 (x) = 0 / 2) birni qo ‘shish (siljish operatori): har bir x uchun A(x) = X +1 ; 3) proyeksiyalash funksiyasi (proyeksiyalash operatori): hamma xl,x2,...,xn lar uchun, Г"{хх,х2,...,хn) = хт ( n = 1,2,...; m = \,2,...,n). Argumentlarining barcha qiymatlarida aniqlangan funksiyani hamma joyda aniqlangan funksiya deb aytamiz. Ravshanki, 3- ta’rifdagi uchala boshlang‘ich funksiya hamma joyda aniqlangan va intuitiv hisoblanuvchi funksiyalardir. Quyidagi uchta qoida vositasi bilan mavjud funksiyalardan yangi funksiyalar hosil qilinadi. Funksiyalar superpozitsiyasi. /„, funksiyalaming qiymatini hisoblash imkoniyatiga ega bo‘lsak, u holda Ip funksiyani quyidagicha hisoblash mumkin: x x, x 2,...,xn o'zgaruvchilarga mos ravishda a ],a 2,...,an qiymatlami beramiz. Hamma f ( a ],a2,...,an) lami hisoblab, b{ = f i ( ax, a 2,...,an)\am\ topamiz. Keyin (p(bl ,b2,...,bm) ni hisoblab, с = Xf/(ax ,а , ,...,an) ni topamiz. Agar (p va / p / 2,•••,/„, lar hamma joyda aniqlangan bo‘lsa, u holda xp funksiya ham hamma joyda aniqlangan boiishi aniq. Haqiqatan ham, agar / , , / 2, l a m i n g hech
bo‘lmaganda birortasi hamma joyda aniqlangan boimasa, u holda Xj/ funksiya hamma joyda aniqlangan boimaydi. Shu bilan birga ikkinchi tomondan, argumentlaming shunday a x, a 2,... , a n qiymatlari topilishi mumkinki, hi = f i ( ax, a 2,...,an) (i = \,m) boisa, (p(bl,b2,...,bm)ni hisoblab boimaydi. Bu holda ham Xj/ funksiya hamma joyda aniqlanmagan boiadi. Shunday qilib, agar (p , f \ , f i , - - - , . f m funksiyalar intuitiv hisoblanuvchi boisa, u holda Xj/ funksiya ham intuitiv hisoblanuvchi boiadi. Shuni ham ta'kidlab o‘tamizki, f \,f 2>•••>/», funksiyalaming barchasi ham xl,x2,...,xn argumentlaming hammasidan bogiiq boim asligi mumkin. Bu hollarda xp funksiyani hosil qilish uchun soxta argumentlardan va I ” (xl,...,xn) funksiyalardan foydalanamiz. Masalan, уf ( x ,y , z ) = (p(ft(x ) , f 2(x ,y,z),y ,x ) funksiya (p(xl, x 2, x 3, x A) va F, (лс, y,z) = f x (.y) , F2 (x, y , z ) = /2 ( x , y , z ) , F3 { x , y , z ) = l \ ( x , y , z) , Fa ( x , v, z ) = I3(x,y,z) funksiyalaming superpozitsiyasidan hosil qilingan. Primitiv (o‘ta sodda) rekursiya sxem asi. (p ( x 2, x 3,...,xn) va xp (xx, x 2,...,xn, x n+x) ( n > 1) funksiyalar berilgan boisin. Quyidagi tengliklarni qanoatlantiruvchi yangi / funksiyani ko‘ramiz: / ( 0 , x 2, x 3,...,xn) = >, x) funksiyaning qiymatini argumentlaming у = 5 , x = 2 qiymatlarida hisoblab chiqaylik. f (0,2) = ’) funksiya va uning muayyan qiymatli x argumenti uchun f(x ,y) = 0 bo'ladigan у argumentlaming eng kichik qiymatlisini topish kerak bo‘lsin. Masalaning yechimi x ga bog‘liq bo'lgani uchun / (xn,_у) = 0 bo'ladigan v ning eng kichik qiymati ham x ning funksiyasi bo‘ladi, ya’ni (4) ifoda quyidagicha o‘qiladi: « у shunday eng kichikki, f( x ,y ) = 0 ». Xuddi shu tarzda ko‘p argumentli < z < y 0) / ( x j , x 2,...,x n,z ) qiymat aniqlanmasligi mumkin. Aniqki, bu holda у ning f ( x l,x2,...,xn,y) = 0 bo‘ladigan eng kichik qiymatini topish jarayoni, y 0gacha yetib bormaydi .
5- t a ’rif. Agar f (x ,, x 2 X(I ) funksiya (p va Ц/ funks iyalardan
(1) munosabat orqali hosil qilinsa, и holda f funksiya (p va \f/
funksiyalardan prim itiv (o ‘ta sodda) rekursiya sxemasi orqali hosil
etilgan deyiladi.
Agar (r va m funksiyalar intuitiv hisoblanuvchi funksiyalar bo‘lsa, u
holda / ham intuitiv hisoblanuvchi funksiya bo‘ladi. Haqiqatan ham,
Х [,Х 2 ,...,Х 3 argumentlaming qiymatlar majmuasi а 1,а ,,...,n )| bo‘lsa, u
holda quyidagilarni ketma-ket topamiz:
Ravshanki, agar (p va \j/ funksiyalar argumentlaming barcha
qiymatlarida aniqlangan bo'lsa, u holda / funksiya ham argumentlaming
barcha qiymatlarida aniqlangan bo'ladi.
Endi primitiv rekursiya sxemasi orqali yangi funksiyalarni hosil qilishni
misollarda ko'ramiz.
1-misol. сp(x) = x va y/(x,y,z) = у +1 bo'lsin hamda / ( v , x )
funksiya quyidagi tengliklar orqali aniqlansin:
f (>>, x) funksiyaning qiymatini argumentlaming у = 5 , x = 2
qiymatlarida hisoblab chiqaylik. f (0,2) =
formulalarning ikkinchisidan ketma-ket ravishda quyidagilarni hosil
/ ( 0 , a 2, a3,...,an) = q>(a2, a 3,...,aH) = b0 ,
f ( l , a 2, a 3,...,an)=xi/(0, b0, a 2, a 3,...,an) = bl,
/ ( 2, a 2, a3 an) = y/(\, bx, a 2, a3 ., a„) = b2 va hokazo.
/ ( 0,x ) = x,
f ( y + \, x) = f ( y , x ) + \.
(2)
qilamiz:
/(1 ,2 ) =V/ (0,2,2) = 2 + 1 = 3,
/( 2 ,2 ) = (1,3,2) = 3 + 1=4,
/(3 ,2 ) = W (2,4,2) = 4 + 1 = 5 ,
/( 4 ,2 ) = у/ (3,5,2) = 5 + 1 = 6 ,
/( 5 ,2 ) = у/ (4,6,2) = 6 + 1 = 7.

f ( y , x) = у + x ekanligini osongina ko‘rsatish mumkin. Haqiqatan ham,

f ( y + z , x ) = f ( y , x ) + z . Bu tenglikda >> = 0 deb qabul qilib,
f ( z , x ) = f ( 0 , x ) + z yoki f ( z , x ) - x + z ni hosil qilamiz. ■
2 - m i s о I. f(y,x) funksiya quyidagi tengliklar bilan berilgan deylik:
bu yerda
f(y,x) funksiyaning qiymatini argumentlaming y = 2 , x = 2 qiymatlari uchun hisoblaymiz. / ( 0,.r) = (p(x) —0 bo‘lganligi uchun
/ (0,2) =
qiymatlarini ketma-ket topamiz:
Bu misolda f ( y , x ) = x -y ekanligini ko‘rsatish mumkin. Haqiqatan
ham, f ( y + z , x ) = f ( y , x ) + z - x . Bu tenglikda jy = 0 deb qabul qilib,
f ( z , x ) = f ( 0 , x ) + z x yoki f ( z ,x ) = z-x ni hosil qilamiz. ■
Minimallash operatsiyasi ( fl -operator). Ixtiyoriy f(x,y) funksiya
berilgan boisin. Quyidagi masalani ко‘rib chiqamiz: x argumentning har
qanday qiymatlari uchun у argumentning hech bo‘lmaganda shunday
bitta qiymatini topish kerakki, / ( x , j ) = 0 boMsin. Masalani yana ham
murakkabroq holda qo'yamiz: berilgan / (x,>’) funksiya va uning
muayyan qiymatli x argumenti uchun f(x ,y) = 0 bo'ladigan у
argumentlaming eng kichik qiymatlisini topish kerak bo‘lsin. Masalaning
yechimi x ga bog‘liq bo'lgani uchun / (дг,_у) = 0 bo'ladigan v ning eng
kichik qiymati ham x ning funksiyasi bo‘ladi, ya’ni
(4) ifoda quyidagicha o‘qiladi: « у shunday eng kichikki, f( x ,y ) = 0 ».
Xuddi shu tarzda ko‘p argumentli
(3)
/(1 ,2 ) = 1 /(0 ,0,2) = 6, = 0 + 2 = 2,
./(2 ,2 ) = if/ (1,2,2) = 2 + 2 = 4.
(p{x) = ц у [ f ( x , y ) = 0] = 0 . (4)
(p(xx , x2,...,xn) = /l y [ f { x x, x 2, . * J = 0 ]. (5)
81
www.ziyouz.com kutubxonasi
6- t a ’rif. f ( x l , x 2,...,xn, y ) funksiyadan f (х ,,х 2,...,х n)
funksiyaga о 'tish fj. -operatorning tatbig'i deb ataladi.
(p(xt , x 2,...,xn) funksiyani hisoblash uchun quyidagi algoritmni
tavsiya etish mumkin.
1. f ( x l , x 2,...,xn,0) ni hisoblaymiz. Agar / ( x p ...,xn,0) = 0 bo‘lsa, u
holda
bo‘lsa, u holda navbatdagi qadamga o‘tamiz.
2. / ( x p x2,...,x;1,l)ni hisoblaymiz. Agar / ( x p ...,x„,l) 0 bo‘lsa, u
holda
holda navbatdagi qadamga o‘tamiz va hokazo. ■
Agar у ning hamma qiymatlari uchun / ( x p ...,xn,y) Ф 0 bo‘Isa, u
holda
у argumentning shunday y 0 qiymati mavjud bo‘lishi mumkinki,
/ ( x 1,x 2,...,x n,y 0) = 0 va, demak, eng kichik у mavjudki,
/(x,,x 2,...,x n, v) = 0 bo‘ladi; shu vaqtning o‘zida, biror z uchun
(0 < z < y 0) / ( x j , x 2,...,x n,z ) qiymat aniqlanmasligi mumkin. Aniqki,
bu holda у ning f ( x l,x2,...,xn,y) = 0 bo‘ladigan eng kichik qiymatini
topish jarayoni, y 0gacha yetib bormaydi. Bu yerda ham

3- misol. f ( x , y ) = x — y funksiya berilgan bo‘lsin. Bu funksiya
minimizatsiya operatori orqali hosil qilinishi mumkin:
/ ( x , y) = jz(y + z = x) = jU2[ /32 (x, у , z) + 1\ (x, y , z ) = l \ (x, у , z ) ] .
Masalan, argumentlaming y = 2 , x = 7 qiymatlarida / ( x , y ) funksiyaning qiymatini (ya’ni, /( 7 ,2 ) ni) hisoblaymiz. Buning uchun v - 2
deb olib, x ga ketma-ket qiymatlar beramiz:
z = 0, 2 + 0-2f* 1,
z = 1, 2 + l = 3*7,
z = 2, 2 + 2 = 4 ^ 7,
z = 3, 2 + 3 = 5 ^ 7 ,
z = 4, 2 + 4 = 6 * 7 ,
z = 5, 2 + 5 = 1 - 1 .
82
Shunday qilib, /(7 ,2 ) = 5 . ■
7- ta ’rif. Agar / ( x , , x 2,...,x n) funksiyani boshlang'ich (oddiy)
funksiyalardan superpozitsiya va primitiv rekursiya sxemasi amallarini
chekli son marta qo 'Hash natijasida hosil qilish mumkin bo ‘Isa, и holda
f (x ,, x2 x n) primitiv rekursiv funksiya deb ataladi.
4- misol. Boshlang'ich 0(x) = 0 , A (x) = x + 1,
1п (х \’х 2т-->х п) = х т 0^m(,a eN ) , f ( x , y ) = x + y , f ( x , y ) = x-y, f(x,y) = x y (x° = 1)
funksiyalar primitiv rekursiv funksiyalar bo'ladi. ■
7.4.2. 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, u 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.
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,.. . , j t ) prim itiv rekursiv (qismiy rekursiv)
funksiya va x,,x 2 x n har xil o ‘zgaruvchilar bo'lsin. Agar har bir i
www.ziyouz.com kutubxonasi
(1 < x < z) uchun z t o'zgaruvchi x l , x 2,—, x n о ‘zgaruvchilarning biri
bo'lsa, и holda / (x ,, x 2,...,xn) = g ( z l, z 2,...,zk) funksiya ham primitiv
rekursiv (qismiy rekursiv) funksiya bo ‘ladi.
I s b о t i . z i = xJj (1 < j i < n) bo‘lsin. U holda
z; =/"(x i,x2,...,x„)
va
y/ ( x l , x 2,. ..,х k) = ф (/''(х ,,х 2, . . . , х „ n ‘k(х], х 2,...,хk))
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.
5- misol. (Soxta argumentlami kiritish.) Agar ф (х1зх3) primitiv
rekursiv funksiya va \f/(xl, x 2, x3) = ф (х,, x3) bo‘Isa, u holda y/(xl,x2.x3)
ham primitiv rekursiv funksiya bo‘ladi. Bu tasdiqni isbot qilish uchun
= X[ va z2 = x 3 deb belgilab, teoremadan foydalanish kifoya. ■
6- misol. ( 0 ‘zgaruvchilaming o‘mini almashtirish.) Agar ф (х ,,х 2)
primitiv rekursiv funksiya va у/(х15х2) = ф(хр х2) boisa, u holda If/
ham primitiv rekursiv funksiya bo‘ladi. Bu tasdiqni isbot qilish uchun
z, = x 2 va z 2 = Xj deb belgilab, teoremadan foydalanish kifoya. ■
7- m i s о 1. ( 0 ‘zgaruvchilarni aynan tenglashtirish.) Agar ф (х ,, x2, x3)
primitiv rekursiv funksiya va \jf(x{, x2) = ф(х,,-х2,х 3) bo‘lsa, u holda
y/(x] ;x 2) ham primitiv rekursiv funksiya bo‘ladi. Bu tasdiqni n = 2 ,
Zj = Xj, z 2 = x 2 , z 3 = x, bo‘lgan holda teoremadan foydalanib isbotlash
mumkin. ■
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 va bu protsedura
bizning algoritm haqidagi intuitiv tasavvurimizga to'g'ri keladi.
Ikkinchidan, hozirgacha qanday muayyan algoritmlar yaratilgan
bo‘lmasin, ular yordamida qiymatlari hisoblanuvchi sonli (arifmetik)
funksiyalar albatta qismiy rekursiv funksiyalar bo‘lib chiqdilar. Shuning
uchun ham hozirgi paytda qismiy rekursiv funksiya tushunchasi algoritm
tushunchasining ilmiy ekvivalenti sifatida qabul qilingan. Buni birinchi
bo‘lib, yuqorida ta’kidlab o‘tganimizdek, ilmiy tezis sifatida A.Chyorch va
S.Klini o ‘rtaga tashladilar.
Xuddi shu kabi har qanday algoritmni mos Tyuring mashinasi
yordamida realizatsiya qilish mumkin. Algoritmning ilmiy ekvivalenti
qismiy rekursiv funksiya bo‘lgani uchun hamma qismiy rekursiv
funksiyalar sinfi A bilan Tyuring mashinalari yordamida hisoblanuvchi
funksiyalar (Tyuring bo'yicha hisoblanuvchi funksiyalar) sinfi В bilan bir
xildir, ya’ni A = В .

XULOSA
1.Hisoblanuvchi funksiyalar va qismiy rekursiv funksiyalar bilan tanishib oldik va ular bilan qanday masalalarga javob toppish mumkinligini ham bilib oldik.

2.Algoritm tushunchasining inuitiv ta’rifi va uning 5 ta xarakteri va xusiyatlari bilan tanishildi;  
3.Rekursiv va rekursiv sanaluvchi to‘plamlar tushunchsi bilan tanishildi; 
4.Algoritm tushunchasining turli talqindagi formal ta’rifinio’rganildi.