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



Download 236,91 Kb.
bet8/17
Sana12.02.2021
Hajmi236,91 Kb.
#58582
1   ...   4   5   6   7   8   9   10   11   ...   17
Bog'liq
AL 13 maruza. NP bilan bogliq muammolar. Hisoblash qobiliyatsizligi

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.


Download 236,91 Kb.

Do'stlaringiz bilan baham:
1   ...   4   5   6   7   8   9   10   11   ...   17




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish