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

Algoritmik yechilmaydigan muammolarga misollar.

1-misol

6 (n) funktsiyani hisoblash, har qanday musbat butun son uchun n 1 ga teng, agar n-ning kasr sonida boshqa raqamlar bilan o'ralgan ketma-ket qatorlar bo'lsa va agar bunday zanjirlar bo'lmasa nolga teng.

2-misol. Gilbertning o'ninchi muammosi, 1900 yilda ishlab chiqilgan P (x1 .., Xm) = 0 shaklidagi ixtiyoriy algebraik Diofantin tenglamalarini yechish algoritmini topish, bu erda P - butun son funktsiyasi (masalan, butun son koeffitsientlari bilan ko'paytirilgan) va xi o'zgaruvchilar. butun sonlar. xn + yn = zn - bu tenglamaning yechimlari Pifagoraliklardir.Fermator teoremasiga ko'ra, bu tenglamada n> 2 uchun nolga teng bo'lmagan butun yechimlar bo'lmaydi.

3-misol. Eyler muammosi - kamida to'rtta har qanday juft son ikkita tub son yig'indisi sifatida ifodalanishi mumkin.