Tyuring mashinasining ishlashi

Algoritmni raqamlash
Algoritmlarni raqamlash ularni o'rganish va tahlil qilishda muhim rol o'ynaydi. Har qanday algoritmni chekli so'z sifatida ko'rsatish mumkin bo'lganligi sababli (ba'zi alifbo belgilarining chekli ketma-ketligi sifatida ifodalanadi) va chekli alifbodagi barcha chekli so'zlar to'plami sanab bo'ladigan bo'lsa, u holda barcha algoritmlar to'plami ham sanab o'tiladi. Bu natural sonlar to‘plami va algoritmlar to‘plami o‘rtasida birma-bir xaritalash mavjudligini, ya’ni har bir algoritmga raqam berish imkoniyatini bildiradi.
Algoritmlarni raqamlash bir vaqtning o'zida barcha algoritmik hisoblangan funktsiyalarni raqamlashdir va har qanday funktsiya cheksiz sonli raqamlarga ega bo'lishi mumkin.
Raqamlashning mavjudligi algoritmlar bilan xuddi raqamlar bilan ishlashga imkon beradi. Raqamlash, ayniqsa, boshqa algoritmlar bilan ishlaydigan algoritmlarni o'rganishda foydalidir.
Boshlang'ich ob'ektlar X to'plami va kerakli ob'ektlar Y to'plami bilan qandaydir massa muammosi bo'lsin. Massa masalasining yechimi mavjudligi uchun X va Y to'plamlarning elementlari konstruktiv ob'ektlar bo'lishi kerak. Shuning uchun bu to'plamlarning elementlarini natural sonlar bilan sanab o'tish mumkin. x∈ X qandaydir boshlang'ich ob'ekt bo'lsin, uning raqamini n(x) bilan belgilang. Agar massa masalasida dastlabki x ob'ektdan n(y) sonli kerakli y∈ Y ob'ektni olish talab etilsa, u holda f arifmetik funktsiyani aniqlaymiz: Nn →N shundayki f(n(x))= n(y).
Ommaviy masalalar uchun arifmetik funktsiyalarni qurishga misol sifatida, massa masalalarini ko'rib chiqing.
1. Agar ] natural sonli massiv berilgan bo‘lsa, u holda uni 2x1, 3x2,... p(n)xn natural son bilan bog‘lash mumkin, bunda p(n) n-tug‘ sondir. Masalan, 5 uzunlikdagi massivni ko'rib chiqing:
] 2x13x25x37x411x5.
Bu raqamlash f arifmetik funksiyasini belgilaydi (masalan, f(73500) = f(22315372110) = 20315272113 = 4891425).
2. Har qanday ratsional son qandaydir natural songa ega. Muammoning kerakli ob'ektlari to'plamini sanab o'tish ahamiyatsiz:
("ha", "yo'q") a (1, 0). Berilgan massa muammosi uchun oldingi misoldagi hiyla yordamida bitta argumentning arifmetik funktsiyasini qurishingiz mumkin yoki uchta argumentning funktsiyasini ko'rib chiqishingiz mumkin (asl uchlik elementlarining uchta soni).
3. Dastur matnlarini raqamlash quyidagicha amalga oshirilishi mumkin: har qanday dasturni 256-ariy sanoq sistemasidagi sonning yozuvi sifatida qabul qilish mumkin (agar dasturni yozish uchun ASCII jadval belgilaridan foydalanilgan bo'lsa).
Ommaviy muammodan arifmetik funktsiyaga o'tish bizga ommaviy muammoning echimi mavjudligi haqidagi savolni arifmetik funktsiyaning qiymatlarini uning argumentidan hisoblashning samarali usuli mavjudligi haqidagi savolga kamaytirishga imkon beradi. s).