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

Yechimi yo’q algoritmni isbotlash usullari

To'g'ridan-to'g'ri usulda Cantor diagonali usuli qo'llaniladi. u quyidagilardan iborat: fikrlash jarayonida ushbu muammoning echimliligi taxminidan tortib, ular qarama-qarshilikka olib keladi.

Bilvosita usul quyidagilardan iborat: o'rganilayotgan muammoning echimliligi allaqachon hal bo'lmaydigan deb topilgan muammoning hal qilinishini anglatadi. Kamaytirish usuli to'g'ridan-to'g'ri usulga qaraganda ko'pincha qulayroqdir. Kamaytirish usulidan foydalanib, ular odatda mustaqil ravishda qiziqtirmaydigan sun'iy muammolarga murojaat qiladilar, ammo buning uchun ularning hal etilmasligini to'g'ridan-to'g'ri isbotlash oson.

Cantorning diagonali usuli

Cantorning son-sanoqsiz haqiqiy sonlari to'plami: natural sonlar to'plami va [0, 1] segmentning haqiqiy raqamlari to'plami har xil kuchlarga ega.

4-misol. Rasmiy arifmetikaning to'liq emasligi haqidagi Godel teoremasi. Har qanday izchil aksiomalar to'plamiga asoslanib isbotlab bo'lmaydigan va rad etilmaydigan ba'zi bayonotlar mavjud (bunday bayonotlar qaytarib bo'lmaydigan deb nomlanadi).