«Algoritmlar nazariyasi»fanidan «Cheklanmagan registrlik mashina.»

Hisoblangan goto: RASP dastur "goto manzili" ni shartli yoki shartsiz sakrashda o'zgartiradigan ko'rsatmalar dastur ko'rsatma.
Ammo bu muammoni hal qilmaydi (agar kimdir murojaat qilmasa) Gödel raqamlari). Bunda dasturning ko'rsatmalarining manzilini olishning usuli yuqori chegaradan "tashqarida / yuqorida" joylashgan (uzoqroq). cheklangan davlat mashinasining ko'rsatmalar registri va JADVAL.
Misol: Faqat to'rtta cheksiz registr bilan jihozlangan hisoblagich mashinasi, masalan. har qanday ikkita sonni (m, n) birga ko'paytirib, p hosil qiladi va shuning uchun m va n sonlari qanchalik katta bo'lmasin, ibtidoiy rekursiv funktsiya bo'ladi; bundan tashqari, buning uchun 20 dan kam ko'rsatma talab qilinadi! masalan. {1: CLR (p), 2: JZ (m, bajarilgan), 3 tashqi halqa: JZ (n, bajarilgan), 4: CPY (m, temp), 5: ichki_ halqa: JZ (m, tashqi_loop), 6: DEC (m), 7: INC (p), 8: J (internal_loop), 9: tashqi_ ilmoq: DEC (n), 10 J (tashqi_ ilmoq), HALT}
Biroq, faqat 4 ta registrga ega bo'lgan ushbu mashina ko'paytirish algoritmini a sifatida bajaradigan RASP qurish uchun deyarli katta emas. dastur. Bizning cheklangan davlat mashinamizni qanchalik katta qilmasligimizdan qat'i nazar, u doimo bo'ladi dastur (shu jumladan uning parametrlari) bu kattaroq. Shunday qilib, Gödel raqamlari kabi cheksiz kodlash fokuslaridan foydalanmaydigan chegaralangan dastur mashinasi bo'lishi mumkin emas universal.
Minsky (1967) bu ko'rsatkichga qarshi ko'rsatma mashinasini (u ularni "dasturiy kompyuter modellari" deb ataydi) {CLR (r), INC (r) va RPT ("a" ko'rsatmalaridan ko'p marta n)} gacha. U bizga muammoni qanday hal qilishni aytmaydi, lekin u buni kuzatadi:
"... dasturiy ta'minot kompyuterida qancha RPT ishlashni davom ettirishini kuzatib borish uchun biron bir usul bo'lishi kerak va bu kompyuterning cheklangan qismida ruxsat berilgan har qanday ma'lum hajmni tugatishi mumkin. RPT operatsiyalari uchun o'zlarining cheksiz registrlari kerak , umuman olganda va ularga biz ko'rib chiqqan operatsiyalarning turlaridan boshqacha munosabatda bo'lish kerak. " (214-bet)
Ammo Elgot va Robinzon muammoni hal qilishadi: ular o'zlarining P-larini ko'paytiradilar₀ Indekslangan ko'rsatmalar to'plami bilan RASP - bilvosita adreslashning biroz murakkabroq (ammo moslashuvchan) shakli. Ularning P '₀ model "asosiy" registr tarkibini (yo'riqnomada ko'rsatilgan) yo'riqnomada aniq ko'rsatilgan "indeks" ga qo'shib (yoki aksincha, "tayanch" va "indeks" ni almashtirib) registrlarga murojaat qiladi. Shunday qilib indeksatsiya P '₀ ko'rsatmalarda indekslanmaydigan P ga qaraganda yana bitta parametr mavjud₀ ko'rsatmalar:
Misol: INC (r_tayanch, indeks ) ; samarali manzil bo'ladi [r_tayanch] + indeks, bu erda tabiiy son "indeks" cheklangan holatdagi mashinalar buyrug'ining o'zidan kelib chiqadi.