«Algoritmlar nazariyasi»fanidan «Cheklanmagan registrlik mashina.»

Xartmanis (1971)

1971 yilga kelib Xartmanis indekslashni soddalashtirdi bilvosita uning RASP modelida foydalanish uchun.
Bilvosita adreslash: Ko'rsatkich registri cheklangan holatdagi mashinaga ko'rsatma uchun zarur bo'lgan maqsadli registrning manzilini etkazib beradi. Boshqa yo'l bilan aytdi: The tarkibi ko'rsatgich registrining manzil ko'rsatma tomonidan ishlatilishi kerak bo'lgan "nishon" registrining. Agar ko'rsatgich registri cheksiz bo'lsa, operativ xotira va uning shassisiga o'rnatilgan mos RASP Turing ekvivalenti bo'ladi. Maqsadli registr yo'riqnomada ko'rsatilganidek, manba yoki manzil registri sifatida xizmat qilishi mumkin.
Shuni esda tutingki, cheklangan holatdagi mashinada ushbu maqsadli registrning manzili aniq ko'rsatilishi shart emas. Faqatgina mashinaning qolgan qismiga shunday deyilgan: menga ko'rsatgich registrida ko'rsatilgan registr tarkibini oling va shu bilan xyz qiling. U ko'rsatma orqali ushbu ko'rsatgich registrini (masalan, "N", yoki "72" yoki "PC" va h.k.) nomlari bilan aniq ko'rsatishi kerak, ammo u ko'rsatgich registrida aslida qaysi raqam borligini bilmasligi shart ( ehtimol 279,431).

Cook and Reckhow (1973) RAMni tavsiflaydi

Kuk va Rekxov (1973) Xartmanis (1971) ni keltiradi va uning modelini ular a deb ataydigan narsalarga soddalashtiradi tasodifiy kirish mashinasi (RAM - ya'ni bilvosita bo'lgan mashina va Garvard me'morchiligi). Bir ma'noda biz Melzakka qaytdik (1961), lekin Melzaknikidan ancha sodda modelga egamiz.

Afzalliklari

Minsky ishlayotgan edi MIT Linkoln laboratoriyasi va u erda o'z asarini nashr etdi; uning qog'ozi nashr etish uchun olingan Matematika yilnomalari 1960 yil 15-avgustda, lekin 1961 yil noyabrgacha nashr etilmagan. Kvitans Melzak va Lambekning asarlari qabul qilinishidan va nashr etilishidan bir yil oldin sodir bo'lgan (1961 yil 15-iyun va 15-iyun kunlari olingan va 1961 yil sentyabrda yonma-yon nashr etilgan) . (I) ikkalasi ham kanadalik bo'lgan va Kanada matematik byulletenida nashr etilgan, (ii) ham Minskiyning asariga murojaat qilmagan bo'lar edi, chunki u hali ham sharhlangan jurnalda chop etilmagan, lekin (iii) Melzak Vang va Lambek ma'lumotnomalariga murojaat qilgan. Melzak, ularning ishi bir vaqtning o'zida va mustaqil ravishda sodir bo'lgan degan farazni keltirib chiqaradi.
Deyarli xuddi shu narsa Shepherdson va Sturgis bilan sodir bo'lgan. Ularning qog'ozi 1961 yilning dekabrida - Melzak va Lambekning ishi olinganidan bir necha oy o'tgach olingan. Shunga qaramay, ular Minskiy asarini ko'rib chiqishdan ozgina (ko'pi bilan 1 oy) foydasiz edilar. Ular izohlarda Ershov, Kafengst va Piterlarning qog'ozlari "yaqinda paydo bo'lgan" (219-bet) ni kuzatishda ehtiyot bo'lishgan. Ular ancha oldin nashr etilgan, ammo nemis tilida nemis jurnallarida nashr etilgan, shuning uchun mavjudlik muammolari o'zlarini namoyon qilmoqda.
Shepherdson va Sturgisning yakuniy maqolasi 1963 yilgacha ekspertlar tomonidan ko'rib chiqilgan jurnalda ko'rinmadi. Va ular o'zlarining A ilovasida adolatli va rostgo'ylik bilan qayd etishganidek, Kafengst (1959), Ershov (1958), Piter (1958) natijalari keyinchalik olingan natijalarga o'xshashdir, natijada quyidagilarni ajratib bo'lmaydi:
0 hosil qiling, ya'ni 0 -> n
sonni ko'paytiring, ya'ni n + 1 -> n
"ya'ni tabiiy sonlarni hosil qiladigan amallarni bajarish" (246-bet)
raqamni nusxalash, ya'ni n -> m
"hisoblash yo'nalishini o'zgartirish" uchun, yoki ikkita raqamni taqqoslash yoki 0 ga qadar kamaytirish
Darhaqiqat, Shepherson va Sturgis xulosa qilishadi