5-mavzu: Algoritmik yechilmaydigan muammolar. Mayxil teoremasi. Algoritmik darjalar

# raqam palindrom ekanligini tekshiring def is_palindrome(n): num = str(n) rev_num = reverse_num(n) return num == rev_num number = 196 step = 0 our_limit = 1000 while (not is_palindrome(number) and step < our_limit): # palindrom topilganda tsiklni to'xtating # yoki bajarilgan iteratsiyalar soni our_limit ga yetdi step = step + 1 rev_num = reverse_num(number) print(rev_num) 'Step', step, ':', number, '+', rev_num, '=', number = number + int(rev_num) # raqamni o'zgartiradi va ikkalasini ham qo'shadi print(number)

Cheksiz tsikllar bilan dasturlar yozishga moyil bo'lgan talabani tasavvur qiling. Cheksiz tsikllarga ega dasturlarni disk raskadrovka qilish va baholash qiyin bo'lishi mumkin. Talaba quyidagi savolni so'raydi: "Python dasturini o'qiydigan va dasturda cheksiz sikl borligini aniqlaydigan dastur yo'qmi?" Afsuski, bunday dastur mavjud emas. Aslida bunday dastur mavjud emasligini matematik tarzda isbotlashimiz mumkin! Agar kimdir bunday dasturni sotmoqchi bo'lsa, u ba'zi dasturlarda cheksiz tsikllarni aniqlashi mumkin, ammo barcha dasturlarda emas. To'xtatish muammosi dasturni (har qanday dasturlash tilida yozilgan) kirish sifatida qabul qiladi va dasturda cheksiz tsikl mavjudligini aniqlaydi. 1936 yilda Alan Turing barcha mumkin bo'lgan dastur-kirish juftliklari uchun to'xtash muammosini hal qilish algoritmi mavjud emasligini isbotladi. Dalilning asosiy qismi Tyuring mashinasi nomi bilan mashhur bo'lgan kompyuter va dasturning matematik ta'rifi edi. 

To'xtash muammosi hal qilib bo'lmaydigan muammoga misoldir. Yechilmaydigan muammolar haqidagi materiallarni o‘qigan har bir kishi “echiladigan” va “yechilmaydigan” atamalariga duch keladi. Chiqarish sifatida “1” (HA) yoki “0” (YO'Q) ni hosil qiladigan masala qaror qabul qilish muammosi deb ataladi. U faqat qaror qabul qiladi. Qaror qabul qilish muammolari dasturlarni yozishda ayniqsa foydali emas, lekin ular murakkablik nazariyasi sohasida hal qiluvchi rol o'ynaydi. Qaror qabul qilish muammosi, agar uni hal qilish algoritmi bo'lmasa, uni hal qilib bo'lmaydi. To'xtatish muammosi hal qilib bo'lmaydigan muammodir. Vang kafel muammosi, Vang kafel postida muhokama qilinganidek, hal-qilib-bo'lmaydi.