13-ma'ruza. Np bilan bog'liq muammolar. Hisoblash qobiliyatsizligi Maruzachi o’qituvchi: katta o’qituvchi Ganihodjayeva Dilfuza Ziyavutdinovna Reja

MT-ni o'chirish muammosi va uning nochorligini isbotlash

• O'sib bo'lmaydiganligi isbotlangan birinchi muammolardan biri.

Uning nochorligini isbotlash diagonal usul va algoritmning o'zini o'zi qo'llash xususiyati yordamida amalga oshiriladi.

• Tugatish muammosi ko'pincha boshqa muammolarning hal qilinmasligini isbotlash uchun foydalaniladi.

Teorema Ixtiyoriy algoritm va uning dastlabki ma'lumotlarining tavsifiga ko'ra (ikkala algoritm va ma'lumotlar Turing mashinasi lentasida belgilar bilan berilgan) ushbu algoritm ushbu ma'lumotlarning to'xtashini yoki to'xtovsiz ishlashini aniqlashga imkon beradigan algoritm (MT) mavjud emas.

Isbot. Natural sonni kirish sifatida qabul qiladigan va natijada natural sonni qaytaradigan barcha algoritmlar to'plamini ko'rib chiqing, ya'ni. xaritalar N -> N *, bu erda N * = N va undef, undef - algoritm halqa qilingan holatda, ya'ni u o'z ishini tugatmagan holat. Ushbu abstraktsiyaga ruxsat beriladi, chunki har qanday cheklangan alifboda so'zlarni tabiiy sonlar bilan noyob kodlash mumkin.

Algoritm berilgan kirishda to'xtashini yoki tinimsiz ishlashini aniqlaydigan universal funktsiya yo'qligini isbotlaymiz. Faraz qilaylik, N * qiymatlarni qabul qiluvchi F (a, x) hisoblash funktsiyasi mavjud. Birinchi argument a bu algoritmning tavsif raqami, biron bir tilda, ikkinchi argument x bu algoritm uchun kirish. F (a, x) ta'rifi bo'yicha x kiritiladigan ma'lumotlar bo'yicha algoritmni bajarish natijasidir.

Hisoblanadigan funktsiya F (a, x) ikkita tabiiy argumentdan iborat bo'lib, BARCHA hisoblash funktsiyalarini bitta tabiiy argument bilan keltiradi. (Tabiiy raqamlar va barcha algoritmlar to'plami shifrlangan deb taxmin qilinadi.) Ushbu funktsiyani amaliylik nuqtai nazaridan ko'rib chiqing, ya'ni. F (x, x), bu erda x raqami bilan algoritm uchun kirish bir xil algoritmning rasmiy yozuvi bo'ladi va h (x) = F (x, x) +1 funktsiyasini tuzing. H (x) funktsiyasi hisoblash mumkin, chunki u F funktsiyasining natijasini ishlatadi va keyin unga bitta funktsiyani qo'shadi. H (x) funktsiya a raqamiga ega bo'lsin, ya'ni F (a, x) = h (x). Ammo ta'rif bo'yicha h (x) = F (x, x) +1 va x = a uchun biz F (a, a) = h (a) va h (a) = F (a, a) +1 ga egamiz. Qarama-qarshilik bor.

Shunday qilib, dastur to'xtab qoladimi yoki yo'qligini aniqlash hisoblanmaydigan vazifadir.

O'chirish muammosining hal qilinmaganligini dasturlarni disk raskadrovka qilishning umumiy algoritmi, aniqrog'i, biron bir dasturning matni va uning ma'lumotlari bilan dastur ushbu ma'lumot uzatiladimi yoki yo'qmi, aniqlaydigan algoritm yo'qligi sifatida izohlanishi mumkin.