«Algoritmlar nazariyasi»fanidan «Cheklanmagan registrlik mashina.»

(1961) Melzakning modeli boshqacha: toshlar uyumlarga va teshiklarga chiqib ketadi

Melzakning (1961) modeli sezilarli darajada farq qiladi. U o'z modelini oldi, lentalarni vertikal ravishda aylantirdi, ularni "tosh toshlari" bilan to'ldirish uchun "erdagi teshiklar" deb atadi. Minskiy "o'sish" va "pasayish" dan farqli o'laroq, Melzak har qanday toshlarni hisoblash va har qanday toshlarni "qo'shish" ni to'g'ri olib tashlashga imkon berdi.
U o'z modeli uchun bilvosita adreslashni belgilaydi (288-bet) va undan foydalanishning ikkita misoli keltirilgan (89-bet); uning modeli ekanligini uning "isboti" (290-292 bet) Turing ekvivalenti shunchalik eskirganki, o'quvchi bilvosita murojaat qilishni isbotlash uchun talab bo'lishini xohlagan yoki xohlamaganligini aniqlay olmaydi.
Melzak modeli merosi Lambekning soddalashtirilganligi va uning Knuk va Rekxou 1973-dagi mnemonik konventsiyalarining paydo bo'lishi.

Lambek (1961) Melzakning modelini Minsky (1961) modeliga aylantiradi: INC va DEC test bilan

Lambek (1961) Melzakning uchlik modelini oldi va uni ikkita bir xil ko'rsatmalarga binoan atomizatsiya qildi - X +, X - agar iloji bo'lsa sakrash - aynan Minskiy (1961) o'ylab topgan ikkita ko'rsatma.
Biroq, Minsky (1961) modeli singari, Lambek modeli ham o'z ko'rsatmalarini sukut bo'yicha ketma-ketlikda bajaradi - X + va X- ikkalasi ham keyingi ko'rsatmaning identifikatorini olib yurishadi, shuningdek X - agar nol bo'lsa, sakrash buyrug'ini bajaradi. -test muvaffaqiyatli o'tdi.

Elgot-Robinson (1964) va RASP muammosi bilvosita murojaat qilmasdan

RASP yoki tasodifiy kirish uchun saqlanadigan dastur mashinasi uning "registrlarida" joylashtirilgan "o'qitish dasturi" bilan hisoblagich mashinasi sifatida boshlanadi. Cheklangan davlat mashinasining "Ko'rsatmalar reestri" ga o'xshash, ammo unga bog'liq bo'lmagan holda, kamida bitta registr ("dastur hisoblagichi" (PC) laqabli) va bir yoki bir nechta "vaqtinchalik" registrlar yozuvlarini olib boradi va ishlaydi, joriy yo'riqnomaning raqami. Cheklangan davlat mashinasining TABLE ko'rsatmalari (i) oqimni olish uchun javobgardir dastur tegishli registrdan ko'rsatma, (ii) dastur ko'rsatma, (iii) tomonidan belgilangan operandlarni olish dastur ko'rsatma va (iv) ning bajarilishi dastur ko'rsatma.
Muammo bundan mustasno: Agar asoslangan bo'lsa hisoblagich kompyuterga o'xshash shassi, fon Neyman mashina Turing ekvivalenti bo'lmaydi. Hisoblanadigan hamma narsani hisoblab chiqa olmaydi. O'z-o'zidan model uning o'lchamlari bilan chegaralanadi (juda-) cheklangan davlat mashinasining ko'rsatmalari. RASP hisoblagichi har qanday narsani hisoblashi mumkin ibtidoiy rekursiv funktsiya (masalan, ko'paytirish), ammo barchasi hammasi emas mu rekursiv funktsiyalar (masalan Ackermann funktsiyasi ).
Elgot-Robinson o'zlarining RASP modellariga dastur ko'rsatmalarini "o'z-o'zini o'zgartirish" imkoniyatini berish imkoniyatini o'rganishadi. Bu g'oya Burks-Goldstine-fon Neyman (1946-7) tomonidan taklif qilingan va ba'zida "hisoblangan goto" deb nomlangan eski g'oya edi. Melzak (1961) "hisoblangan goto" ni nomi bilan alohida tilga oladi, ammo uning modelini bilvosita adreslash bilan ta'minlaydi.