Albatta. Buni ko'rsatish qiyin emas =(X y) + (Y X) endi olingan natijalar 1 misolidan va 3 misolidan kelib chiqadi. Minimallashtirish jarayoni. N-mahalliy funktsiya G(x1, x2,..., xn) (n+1)-mahalliy funktsiyasi f(x1,x2,..., xn,y) minimallashtirish operatsiyalari yoki eng kam sonli operator yordamida, agar har qanday x1, x2,..., xn,y tenglik g(x1, x2,..., xn)=y keyin va faqat qachon amalga oshiriladi: 1) F(x1,x2,..., xn, t) belgilangan va f(x1,x2,..., xn, t)>0 har qanday 0≤t
4-misol.
Keling, bu – ibtidoiy rekursiv funktsiya ekanligini ko'rsataylik.
Haqiqatan ham. =(X Y)+(Y X)
ekanligini ko'rsatish oson
Endi natija 1-misol va 3-misoldan kelib chiqadi.
Minimallashtirish jarayoni. Minimalizatsiya operatsiyasidan yoki eng kichik sonli operatordan foydalangan holda (n + 1) joyidagi F (x1, x2, ..., xn, y) funktsiyadan olingan n-ary funktsiya G (x1, x2, ..., xn). har qanday x1, x2,…, xn, y uchun g (x1, x2,…, xn) = y tenglik quyidagicha bo'ladi va agar shunday bo'lsa:
1) har qanday 0≤t 0;
2) F (x1, x2, ..., xn, y) = 0.
Agar 1), 2) shartlardan birortasi bajarilmasa, u holda x (x1, x2,…, xn) funktsiya x1, x2,…, xn uchun aniqlanmagan. Xulosa qilib aytganda, G (x1, x2, ..., xn) qiymati y argumentning oxirgi tenglik bajarilgan eng kichik qiymatiga teng.
Quyidagi yozuv ishlatiladi: G (x1, x2,…, xn) = Mening [F (x1, x2,…, xn, y) = 0].
Minimalizatsiya operatsiyasi yordamida g funktsiyasi F funktsiyasidan olinadi deyiladi.
Misol 5: qisman raqamli funktsiya qisman recursiv ekanligini isbotlash. Birinchidan, ushbu funktsiya minimallashtirish operatsiyalari yordamida funktsiyadan olinganligini unutmang, ya'ni. = My. 2 va 4 misollariga ko'ra, funktsiya ibtidoiy recursivdir. Bu degani, qisman rekursiv funktsiya. Ushbu misol, Prp klassi Pp sinfidan ancha kengroq ekanligini ko'rsatadi. Pp klassi Pnp sinfidan ancha kengroq, ya'ni Prp bilan PP bilan Pnp deb aytish mumkin.
Turing va Church tezislari. Algoritmning asosiy xususiyatlaridan biri shundaki, u har bir muammoni hal qilish uchun kerakli cheksiz ko'p sonli vazifalarni bajarish uchun bir qator qadamlarni topishga imkon beruvchi yagona usuldir. Algoritm tushunchasi nuqtai bir oz boshqacha nazaridan qarash mumkin. Vazifalarning cheksiz to'plamidagi har bir vazifa ba'zi bir alifbo so'zlari bilan ifodalanishi mumkin (kodlangan) va muammoni bir xil alfavitning boshqa so'zlari bilan hal qilish mumkin. Natijada, tanlangan alfavitning barcha so'zlari to'plamining bir qismida berilgan funktsiyani olamiz va bir xil alfavitning barcha so'zlarida qiymatni qabul qilamiz. Har qanday muammoni hal qilish uchun ushbu funktsiyaning ma'nosini ushbu muammoni kodlovchi so'zda topish kerak. Va bu sinfning barcha muammolarini hal qilish uchun algoritmga ega bo'lish-bu bitta usulga ega bo'lish demakdir, bu esa o'z navbatida aniqlangan maydondan argumentning har qanday qiymatlari uchun qurilgan funktsiyaning qiymatini "hisoblash" bosqichlarining yakuniy soniga imkon beradi. Shunday qilib, algoritmik muammo.
Funktsiyaning qiymatini hisoblash nimani anglatishini aniqlab olish kerak. Bu funktsiyaning qiymatini mos turing mashinasi yordamida hisoblash demakdir. Qaysi funktsiyalar uchun ularning turing hisoblash mumkin? Olimlarning ko'plab tadqiqotlari shuni ko'rsatdiki, bunday funktsiyalar klassi juda keng. Har bir funktsiya, har qanday algoritm mavjud bo'lgan qiymatlarni hisoblash uchun, ba'zi turing mashinasi tomonidan hisoblab chiqilgan. Bu turing algoritm nazariyasi yoki turing tezisining asosiy gipotezasi deb nomlangan quyidagi gipotezani ifodalashga sabab bo'ldi.
Tezis Turing. Funktsiya qadriyatlarini topish uchun, ma'lum bir alifboda berilgan, keyin faqat ba'zi algoritm mavjud, funktsiya turing tomonidan hisoblab chiqilgan bo'lsa, ya'ni. u tegishli turing mashinasida hisoblanishi mumkin. Bu shuni anglatadiki, turing funktsiyasi bo'yicha hisoblangan qattiq matematik kontseptsiya tajribadan olingan algoritm kontseptsiyasining ideal modelidir. Ushbu dissertatsiya Axiom, postulatdan boshqa hech narsa emas, tajribamizning ushbu tajriba ostida olib kelishni istagan matematik nazariya bilan bo'lgan aloqalari haqida. Albatta, bu tezis asosan matematika usullari bilan isbotlanishi mumkin emas, chunki u matematik xususiyatga ega emas (tezisdagi bir tomon – algoritm tushunchasi – aniq matematik tushuncha emas). U tajriba asosida ilgari suriladi va uning hayotiyligini tasdiqlaydigan tajriba.
Biroq, turing tezisining rad etilishi haqidagi asosiy imkoniyat yo'q. Buning uchun har qanday algoritm bilan hisoblangan funktsiyani ko'rsatish kerak, lekin turing mashinasida hisoblanmaydi. Ammo bunday imkoniyat juda kam ko'rinadi. Turing tezisiga o'xshab, Church tezisining nomi bilan atalgan tegishli gipoteza recursiv funktsiya nazariyasida ilgari suriladi.
Cherkovning tezisi. Raqamli funktsiya faqat rekursiv bo'lsa, algoritmik ravishda hisoblab chiqiladi.
Va bu farazni qat'iy matematik ravishda isbotlab bo'lmaydi, uni amaliyot, tajriba tasdiqlaydi, chunki u amaliyot va nazariyani bog'lash uchun mo'ljallangan. Matematikada ko'rib chiqilgan, algoritmik ma'noda hisoblanadigan barcha aniq funktsiyalar rekursiv bo'lib chiqdi.
Biz bir nechta nazariyalar bilan tanishdik, ularning har biri algoritm tushunchasini aniqlab beradi. Ushbu nazariyalar bir-biri bilan qanday bog'liqligi haqida savol tug'iladi. Javob quyidagi teorema bilan berilgan.
Teorema. Quyidagi funktsiyalar sinflari (tabiiy sonlar bo'yicha aniqlangan va tabiiy qiymatni olgan) mos keladi.
1) Tyuring tomonidan hisoblanadigan barcha funktsiyalar klassi;
2) barcha rekursiv funktsiyalar klassi.
Bu endi gipoteza yoki tezis emas, balki qat'iy isbotlangan matematik teorema.
Shuni ta'kidlash kerakki, algoritmlarning boshqa nazariyalari ham mavjud va ularning barchasi uchun ularning ko'rib chiqilayotgan nazariyalar bilan tengligi ham isbotlangan.
936 yilda Cherkov predikatlar mantig'ining har bir formulasi uchun qoniqarli yoki umuman yaroqli bo'lishini aniqlashga imkon beradigan algoritm yo'qligini isbotladi.
Matematikadagi eng mashhur algoritmik muammolardan biri Xilbertning 10-masalasi bo'lib, u 1901 yilda Xalqaro matematik kongressida boshqalar qatoriga qo'ygan. Diofantning har qanday tenglamasi uchun uning butun sonli echimi borligini aniqlaydigan algoritmni topish talab qilindi.
Diofantin tenglamasi bu erda butun son ko'rsatkichlari va butun son koeffitsientlari bo'lgan polinom bo'lgan formadagi tenglama. Umuman olganda, bu muammo uzoq vaqt davomida echimini topmadi va faqat 1970 yilda sovet matematikasi Yu.V.Matiyasevich o'zining hal qilib bo'lmasligini isbotladi.
Xulosa qilib aytganda, yana bir bor ta'kidlaymizki, algoritmik noaniqlik faqat ma'lum bir cheksiz qatorning barcha masalalarini echish uchun yagona usulning yo'qligini anglatadi, shu bilan birga har bir alohida muammo uchun uni individual tarzda hal qilish mumkin. Masalan, Diofant tenglamasining butun sonli echimga ega yoki yo'qligini aniqlaydigan yagona algoritm yo'qligiga qaramay, ma'lum bir holat uchun Diofantning tenglamasi
Diofant tenglama – bu turning tenglamasi bo'lib, unda- butun daraja ko'rsatkichlari va butun koeffitsientlar bilan polinom. Umuman olganda, bu muammo uzoq vaqt davomida hal qilinmagan va faqat 1970da sovet matematikasi yu. V. Matiyasevich uning hal etilmasligini isbotladi. Xulosa qilib aytganda, algoritmik ajralmaslik bu cheksiz ketma-ketlikning barcha muammolarini hal qilishning yagona usuli yo'qligini anglatadi, ayni paytda har bir individual vazifa alohida tarzda hal qilinishi mumkin. Misol uchun, Diofant tenglamasi tamsayı hal etadimi yoki yo'qligini aniqlaydigan yagona algoritm yo'qligiga qaramasdan, Diofant tenglamasi uchun Ma'lumki, uning barcha ildizlarini erkin penisning bo'luvchilari orasida izlash kerak
Diofant tenglama – bu turning tenglamasi bo'lib, unda-butun daraja ko'rsatkichlari va butun koeffitsientlar bilan polinom. Umuman olganda, bu muammo uzoq vaqt davomida hal qilinmagan va faqat 1970da sovet matematikasi yu. V. Matiyasevich uning hal etilmasligini isbotladi. Xulosa qilib aytganda, algoritmik ajralmaslik bu cheksiz ketma-ketlikning barcha muammolarini hal qilishning yagona usuli yo'qligini anglatadi, ayni paytda har bir individual vazifa alohida tarzda hal qilinishi mumkin. Misol uchun, Diofant tenglamasi tamsayı hal etadimi yoki yo'qligini aniqlaydigan yagona algoritm yo'qligiga qaramasdan, Diofant tenglamasi uchun Ma'lumki, uning barcha ildizlarini erkin penisning bo'luvchilari orasida izlash kerak
O’Z O’ZINI NAZORAT QILISH uchun savollar:
1. Turing mashinasi deganda nimani tushunasiz?
2. Tyuring mashinasi qaysi qismlardan iborat?
3. Mashina so'zining ta'rifini bering.
4. Qanday funktsiya raqamli deb nomlanadi?
5. Qanday funktsiya qisman raqamli deb ataladi?
6. Turing hisoblanadigan funktsiyasining ta'rifini bering.
7. Eng oddiy funktsiyalar qanday?
8. Superpozitsiya operatsiyasining ta'rifini bering.
9. Ibtidoiy rekursiya operatsiyasining ta'rifini bering.
10. Minimallashtirish operatsiyasining ta'rifini bering.
11. Cherkovning tezisini tuzing.
12. Tyuring tezisini tuzing.
13. Turing hisoblanadigan funktsiyalari va qisman rekursiv funktsiyalari o'rtasidagi bog'liqlik qanday?
|
