Mavzu: Algoritmlarning matematika bilan bog’liqligi (8 soat) Reja

3. Chorch tezisi

Chorch-Tyuring tezisi - algoritmik hisoblashning intuitiv tushunchasi va qisman rekursiv funktsiya va Tyuring mashinasida hisoblanishi mumkin bo'lgan funktsiyaning qat'iy rasmiylashtirilgan tushunchalari o'rtasidagi ekvivalentlik haqidagi gipotezadir.

Algoritmik hisoblashning dastlabki kontseptsiyasining intuitiv tabiati tufayli bu tezis ushbu kontseptsiya bo'yicha hukm xarakteriga ega va uni qat'iy isbotlab yoki rad etib bo'lmaydi.
Hisoblash funksiyasining aniq ta'rifidan oldin matematiklar qog'oz va qalam usullari yordamida hisoblanishi mumkin bo'lgan funktsiyalarni tavsiflash uchun ko'pincha "samarali hisoblash" norasmiy atamasini ishlatishgan.
Tezis 1930-yillarning o'rtalarida Chorch va Alan Turing tomonidan ilgari surilgan. Ushbu tezis matematik mantiq, informatika, kibernetika kabi fan va fan falsafasining ko'plab sohalari uchun zarur.
Rekursiya nazariyasi nuqtai nazaridan, tezis umumiy rekursiv funktsiyalar sinfi tomonidan hisoblashning intuitiv tushunchasining aniq tavsifi sifatida tuzilgan. Ushbu formula ko'pincha oddiy chorch tezisi deb ataladi.
Stiven Klin tomonidan algoritmlar tomonidan hisoblab chiqiladigan barcha qisman (ya'ni barcha argument qiymatlari uchun aniq belgilanmagan) funktsiyalar qisman rekursiv ekanligi haqida umumiyroq formula berilgan.
Turingning hisoblash qobiliyati nuqtai nazaridan, tezisda aytilishicha, har qanday algoritmik hisoblab chiqiladigan funksiya uchun uning qiymatlarini hisoblaydigan Tyuring mashinasi mavjud. Ba'zida bu formula Tyuring tezisi sifatida paydo bo'ladi. Tyuring ma'nosida qisman hisoblanuvchi va qisman rekursiv funktsiyalar sinflari bir-biriga to'g'ri kelishini hisobga olgan holda, bayonot yagona Chorch-Tyuring tezisiga birlashtirilgan.


4. Algoritmlar nazariyasining tadbiqlari


Dumli rekursiya. Barcha rekursiyalar uchun aniqlanayotgan to’plam yoki funksiyaning ma’lumotlari o’zida jamlanishi kerak. Bunaqa ma’lumotlarning juda ko’p turlari joriy etilishi mumkin. Bu ma’lumotlardan ko’p marotaba, turli yo’sinlarda foydalanish mumkin. Rekursiyaning turli darajalari mavjud bo’lib, ularning murakkablik darajalari ham turlicha. Quyida, bunday turlarning ba’zilari muhokama qilinadi. Ularning oddiysi – dumli rekursiya. Dumli rekursiya faqatgina bitta rekursiv murojaatni funksiya oxirida qo’llash orqali harakterlanadi.Boshqacha qilib aytganda, murojaat bo’lganda, funksiya orqali amalga oshirilishi kerak bo’lgan birorta so’z qolmaydi; rekursiv murojaat eng so’nggi emas, unda erta bo’lmagan, to’g’ridan-to’g’ri yoki o’zlashtirma turdagilari ham mavjud. Misol uchun, tail() funksiyasi quyidagicha aniqlanadi:
void tail(int i){
if(i>0){cout<
tail(i-1);}
}
tail (dumli ) rekursiya li funksiyaga misol, bundaki nonTail funksiyasi quyidagicha izohlanadi:
void nonTail(int i) {
if (i > 0) {
nonTail(i-1);
cout << i << '';
nonTail(i-1);
}
}
Dumli rekursiya qurilishi oddiygina va kimdir tomonidan osonlikcha joylashtirilishi mumkin. Buni quyidagi I o’zgaruvchining qiymatini unga bo’lgan rekursiv murojaatlar darajasi orqali kamaytirib borish misolida ko’rish mumkin. Bunda, tail() iterativ funksiya orqali ifodalanishi mumkin:
void iterativeEquivalentOfTail(int i) {
for ( ; i > 0; i--)
cout << i << '';
}
Dumli rekursiyani iteratsiya orqali foydalanishning afzalligi mavjudmi? C++ kabi tillar uchun, solishtiriladigan hech qanday foydali tomonlari bo’lmasligi mumkin, lekin Prolog kabi tillarda bu juda kata ahamiyatga ega bo’ladi. If goto bilan birga qo’llaniladigan hollarda dumli rekursiyadan foydalanmaslik ma’qul.