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

Hisoblanmaydigan arifmetik funktsiyalar to'plamining kardinalligini baholash.

 

Hisoblanmaydigan arifmetik funktsiyalar son-sanoqsizdir.

O'z-o'zini qo'llash va o'chirish bilan bog'liq muammolar.

Ushbu muammolar ko'pincha boshqa muammolarning echimsizligini ularni kamaytirish orqali isbotlash uchun ishlatiladi.

Algoritmni raqamlash

Turing mashinasi (algoritmi) soniga ko'ra dasturini (algoritm tavsifi) tiklaydigan hisoblash funktsiyasi mavjud N: N → A. Bunday funktsiya algoritmlarni raqamlash deb ataladi. Bu sizga algoritmni uning raqami bilan aniqlashga imkon beradi. Agar ϕ (n) = A bo'lsa, u holda n soni A algoritmining soni deb ataladi, xaritaning o'zaro o'ziga xosligidan kelib chiqqan holda function-1 teskari funktsiyasi mavjud, bu algoritm An tavsifiga ko'ra tiklanadi, bu raqamlashda uning raqami ϕ-1 (An) = n.

Raqamlashning mavjudligi raqamlar bilan bo'lgani kabi algoritmlar bilan ishlashga imkon beradi. Bu algoritmlarni algoritmlarni tadqiq qilishda ayniqsa foydalidir.