Stroj s náhodným přístupem - Random-access machine

V počítačové vědě je stroj s náhodným přístupem ( RAM ) abstraktní stroj v obecné třídě registračních strojů . RAM je velmi podobná počítači s čítačem, ale s přidanou schopností „nepřímého adresování“ jeho registrů. Stejně jako čítač má RAM své instrukce v konečné části stroje (takzvaná harvardská architektura ).

Ekvivalent RAM univerzálního Turingova stroje  -s programem v registrech i s daty-se nazývá stroj s uloženým programem s náhodným přístupem nebo RASP. Je příkladem takzvané von Neumannovy architektury a má nejblíže k běžnému pojmu počítač .

Společně s modely Turingových strojů a počítačů proti obráběcím strojům se pro analýzu složitosti výpočtu používají modely RAM a RASP . Van Emde Boas (1990) nazývá tyto tři plus modely ukazovacího stroje „sekvenční stroj“, aby je odlišil od modelů „ paralelních strojů s náhodným přístupem “.

Úvod do modelu

Koncept stroje s náhodným přístupem (RAM) začíná nejjednodušším modelem ze všech, takzvaným modelem čítače . Dva přírůstky jej však posunuly od počítadla. První vylepšuje stroj o pohodlí nepřímého adresování; druhá posune model směrem ke konvenčnějšímu počítači na bázi akumulátorů s přidáním jednoho nebo více pomocných (vyhrazených) registrů, z nichž nejběžnější se nazývá „akumulátor“.

Formální definice

RAM stroj (RAM) je abstraktní výpočetní stroj stejný model vícenásobné registru čítače stroj s přidáním nepřímé adresování. Podle uvážení instrukce z TABULKY stroje s konečným stavem stroj odvozuje adresu „cílového“ registru buď (i) přímo ze samotné instrukce, nebo (ii) nepřímo z obsahu (např. Číslo, štítek) registr "ukazatel" uvedený v pokynu.

Podle definice: Registr je místo s adresou (jedinečným rozlišitelným označením/lokátorem ekvivalentní přirozenému číslu) a obsahem  - jediným přirozeným číslem. Pro přesnost použijeme kvaziformální symboliku z Boolos-Burgess-Jeffrey (2002) k určení registru, jeho obsahu a operace na registru:

• [r] znamená „obsah registru s adresou r“. Štítek „r“ zde je „proměnná“, kterou lze vyplnit přirozeným číslem nebo písmenem (např. „A“) nebo jménem.
• → znamená „kopírovat/uložit do“ nebo „nahrazuje“, ale bez zničení zdroje

Příklad: [3] +1 → 3; znamená "Obsah zdrojového registru s adresou" 3 ", plus 1, je vložen do cílového registru s adresou" 3 "(zde je zdroj a cíl na stejném místě). Pokud [3] = 37, tj. obsah registr 3 je číslo „37“, pak bude do registru 3 vloženo 37+1 = 38.

Příklad: [3] → 5; znamená "Obsah zdrojového registru s adresou" 3 "je vložen do cílového registru s adresou" 5 ". Pokud [3] = 38, to znamená, že obsah registru 3 je číslo 38, pak toto číslo bude vloženo do registr 5. Obsah registru 3 není touto operací narušen, takže [3] je nadále 38, nyní stejné jako [5].

Definice: Přímá instrukce je taková, která v samotné instrukci uvádí adresu zdrojového nebo cílového registru, jehož obsah bude předmětem instrukce. Definice: Nepřímá instrukce je ta, která specifikuje „registr ukazatele“, jehož obsahem je adresa „cílového“ registru. Cílový registr může být buď zdroj, nebo cíl (příkladem jsou různé instrukce COPY). Registr se může adresovat nepřímo.

Pro nedostatek standardu/konvence bude tento článek v instrukci specifikovat „přímý/nepřímý“, zkráceně „d/i“, jako parametr (nebo parametry):

Příklad: COPY ( d , A, I , N), prostředky přímo d získat adresu zdrojového registru se registr ( „A“) od samotného instrukce, ale nepřímo i získat cílovou adresu z ukazatel registraci N. Předpokládejme, [N] = 3, pak je registr 3 cílem a instrukce provede následující: [A] → 3.

Definice: Obsah zdrojového registru používá instrukce. Adresu zdrojového registru lze zadat buď (i) přímo instrukcí, nebo (ii) nepřímo registrem ukazatele specifikovaným instrukcí.

Definice: Obsahem registru ukazatelů je adresa „cílového“ registru.

Definice: Obsah registru ukazatele ukazuje na cílový registr  - „cíl“ může být buď zdrojový nebo cílový registr.

Definice: Cílový registr je místo, kde instrukce uloží svůj výsledek. Adresu zdrojového registru lze zadat buď (i) přímo instrukcí, nebo (ii) nepřímo registrem ukazatele specifikovaným instrukcí. Zdrojový a cílový registr mohou být jeden.

Refresher: Counter-machine model

Melzak (1961) poskytuje snadnou vizualizaci pultového stroje: jeho „registry“ jsou otvory v zemi a tyto otvory drží oblázky. Na pokyn do a ven z těchto otvorů „počítač“ (osoba nebo stroj) přidá (INCrements) nebo odebere (DECrements) jeden oblázek. Podle potřeby přicházejí další oblázky a přebytečné oblázky se vracejí zpět do nekonečné zásoby; pokud je otvor příliš malý na to, aby pojal oblázky, „počítač“ vykopá otvor větší.

Minsky (1961) a Hopcroft-Ullman 1979 (s. 171) nabízejí vizualizaci vícepáskového Turingova stroje s tolika páskami s levým koncem, kolik má „registrů“. Délka každé pásky je neomezená doprava a každý čtverec je prázdný, kromě levého konce, který je označen. Vzdálenost pásku je „hlava“ od jeho levého konce, měřená v počtu pásky čtverců, představuje přirozené číslo v „registr“. K SNÍŽENÍ počtu čtverců se hlava pásky pohybuje doleva; INCrement se pohybuje doprava. Na pásku není nutné tisknout ani mazat značky; jedinou podmíněnou instrukcí je zkontrolovat, zda je hlava na levém konci, testováním značky na levém konci s „instrukcí Jump-if-checked“.

Následující instrukce „mnemotechnika“, např. „CLR (r)“ jsou libovolné; žádný standard neexistuje.

Registr Stroj má na paměti vně jeho konečný-státní stroj - nespoutaný (CF: poznámka pod čarou | spočetnou a neomezenou) sbírku diskrétních a jedinečně označených místech s nespoutanou kapacitou, zvanou „registry“. Tyto registry obsahují pouze přirozená čísla (nula a kladná celá čísla). Podle seznamu sekvenčních instrukcí v TABLE stroje konečného stavu pracuje s obsahem těchto „registrů“ několik (např. 2) typů primitivních operací. Nakonec je k dispozici podmíněný výraz ve formě IF-THEN-ELSE k otestování obsahu jednoho nebo dvou registrů a "rozvětvení/skok" konečného stavového stroje z výchozí sekvence instrukcí.

Základní model 1 : Model nejbližší Minskyho (1961) vizualizaci a Lambek (1961):

• {INCrement contents of register r, DECrement contents of register r, IF contents of register r is Zero THEN Jump to instruction I _z ELSE continue to next instruction}:

Návod	Mnemotechnická pomůcka	Akce na rejstřících „r“	Akce na instrukčním registru konečného stavu stroje, IR
Přírůstek	INC (r)	[r] + 1 → r	[IR] + 1 → IR
DECrement	DEC (r)	[r] - 1 → r	[IR] + 1 → IR
Skoč, pokud nula	JZ (r, z)	žádný	IF [r] = 0 POTOM z → IR JINAK [IR] + 1 → IR
Stůj	H	žádný	[IR] → IR

Základní model 2 : „Nástupnický“ model (pojmenovaný po nástupnické funkci axiomů Peano ):

• {ZVÝŠTE obsah registru r, CLeaR obsah registru r, IF obsah registru r _j Rovná se obsahu registru r _k PAK Skočte na instrukci I _z DALŠÍ přejděte na další instrukci}

Návod	Mnemotechnická pomůcka	Akce na rejstřících „r“	Akce na instrukčním registru konečného stavu stroje, IR
Průhledná	CLR (r)	0 → r	[IR] + 1 → IR
Přírůstek	INC (r)	[r] + 1 → r	[IR] + 1 → IR
Skočte, pokud je to stejné	JE (r1, r2, z)	žádný	IF [r1] = [r2] PAK z → IR JINÉ [IR] + 1 → IR
Stůj	H	žádný	[IR] → IR

Základní model 3 : Používá Elgot-Robinson (1964) při vyšetřování ohraničených a neomezených RASP-„nástupnický“ model s COPY místo CLEAR:

• {ZVÝŠTE obsah registru r, Zkopírujte obsah registru r _j do registru r _k , IF obsah registru r _j Rovná se obsahu registru r _k pak Přejít na instrukci I _z JINÉ přejít na další instrukci}

Návod	Mnemotechnická pomůcka	Akce na rejstřících „r“	Akce na instrukčním registru konečného stavu stroje, IR
KOPÍROVAT	KOPÍROVAT (r1, r2)	[r1] → r2	[IR] + 1 → IR
Přírůstek	INC (r)	[r] + 1 → r	[IR] + 1 → IR
Skočte, pokud je to stejné	JE (r1, r2, z)	žádný	IF [r1] = [r2] PAK z → IR JINÉ [IR] + 1 → IR
Stůj	H	žádný	[IR] → IR

Vytváření „praktických pokynů“ ze základních sad

Tři základní sady 1, 2 nebo 3 výše jsou ekvivalentní v tom smyslu, že je možné vytvořit instrukce jedné sady pomocí pokynů jiné sady (zajímavé cvičení: nápověda od Minskyho (1967) - deklarujte vyhrazený registr, např. Volání „0“ (nebo Z pro „nulu“ nebo E pro „vymazání“) obsahuje číslo 0). Volba modelu bude záviset na tom, který autor považuje za nejsnazší použití při demonstraci nebo důkazu atd.

Navíc ze základních sad 1, 2 nebo 3 můžeme vytvořit libovolnou z primitivních rekurzivních funkcí (viz Minsky (1967), Boolos-Burgess-Jeffrey (2002)). (Jak přetypovat síť širší, aby zachytila celkové a částečné rekurzivní funkce mu bude diskutováno v kontextu nepřímého adresování). Budování primitivních rekurzivních funkcí je však obtížné, protože sady instrukcí jsou tak ... primitivní (drobné). Jedním z řešení je rozšířit konkrétní sadu o „praktické pokyny“ z jiné sady:

Nepůjde o podprogramy v konvenčním smyslu, ale spíše o bloky instrukcí vytvořené ze základní sady a dané mnemotechnickou pomůckou. Ve formálním smyslu, abychom tyto bloky mohli použít, je musíme buď (i) „rozšířit“ na jejich ekvivalenty základní instrukce-budou vyžadovat použití dočasných nebo „pomocných“ registrů, takže model s tím musí počítat, nebo ( ii) navrhněte naše stroje/modely podle pokynů „vestavěných“.

Příklad: Základní sada 1. K vytvoření CLR (r) použijte blok instrukcí k odpočtu registru r na nulu. Sledujte použití výše uvedeného nápovědy:

• CLR (r) = _ekv
• smyčka : JZ (r, exit )

• DEC (r)
• JZ (0, smyčka )

• výstup : atd.

To vše je pouze pro pohodlí; nic z toho nezvyšuje vnitřní sílu modelu.

Například: nejrozšířenější sada bude zahrnovat každou jedinečnou instrukci ze tří sad, plus bezpodmínečný skok J (z), tj .:

• {CLR (r), DEC (r), INC (r), CPY (r _s , r _d ), JZ (r, z), JE (r _j , r _k , z), J (z)}

Většina autorů si vybere jeden nebo druhý z podmíněných skoků, např. Shepherdson-Sturgis (1963) používá výše uvedenou sadu minus JE (aby byli naprosto přesní, místo JZ používají JNZ-Jump if Not Zero; další možná praktická instrukce).

"Nepřímá" operace

Příklad nepřímého adresování

V našem každodenním životě není pojem „nepřímé operace“ neobvyklý.

Příklad: hon na poklad.

Na místě „Tom _ & _ Becky's_cave_in_pirate_chest“ bude místo, kde najdeme mapu, která nás nasměruje na „poklad“:

(1) Jdeme na místo „Tom _ & _ Becky's_cave ...“ a kopeme kolem, dokud nenajdeme dřevěnou bednu

(2) Uvnitř krabice je mapa umístění pokladu: „under_Thatcher's_front_porch“

(3) Jdeme na místo „under_Thatcher's_front_porch“, sbíjíme beton a objevujeme „poklad“: pytel rezavých dveřních klik.

Indirection určuje umístění označené jako pirátská truhla v „Tom _ & _ Becky's_cave ...“, které funguje jako ukazatel na jakékoli jiné místo (včetně sebe): jeho obsah (mapa pokladu) poskytuje pod_Thatcher „adresu“ cílového umístění „ 's_front_porch ", kde dochází ke skutečné akci.

Proč potřeba nepřímé operace: Dva hlavní problémy s modelem pultového stroje

V následujícím si musíme pamatovat, že tyto modely jsou abstraktní modely se dvěma zásadními rozdíly od čehokoli fyzicky reálného: neomezený počet registrů, každý s neomezenými kapacitami. Problém se nejdramatičtěji objevuje, když se člověk pokusí použít model obráběcího stroje k vytvoření RASP, který je Turingovým ekvivalentem, a tedy vypočítat jakoukoli částečnou rekurzivní funkci mu :

• Melzak (1961) přidal do svého modelu „děr a oblázků“ nepřímou orientaci, aby se jeho model mohl modifikovat „vypočítaným přechodem“, a uvádí dva příklady jeho použití („Desetinná reprezentace v měřítku d“ a „Řazení podle magnituda “, zda jsou použity v jeho důkazu, že model je Turingův ekvivalent, není jasné, protože„ samotný program je ponechán na čtenáři jako cvičení “(str. 292)). Minsky (1961, 1967) byl schopen prokázat, že s vhodným (ale obtížně použitelným) Gödelovým kódováním čísel registrační model nepotřeboval indirection, aby byl Turingovým ekvivalentem; ale potřeboval alespoň jeden neomezený registr. Jak je uvedeno níže, Minsky (1967) naznačuje problém pro RASP, ale nenabízí řešení. Elgot a Robinson (1964) prokázali, že jejich model RASP P ₀  - nemá žádnou možnost přesměrování - nemůže vypočítat všechny „rekurzivní sekvenční funkce“ (ty, které mají parametry libovolné délky), pokud nemá schopnost modifikovat vlastní instrukce, ale může to přes Gödel čísla, pokud ano (str. 395-397; zejména obrázek 2 a poznámka pod čarou str. 395). Na druhé straně jejich RASP model P ' ₀ vybavený "indexovým registrem" (nepřímé adresování) dokáže vypočítat všechny "částečné rekurzivní sekvenční funkce" (rekurzivní funkce mu) (str. 397-398).

Cook a Reckhow (1973) to říkají nejvýstižněji:

Nepřímé pokyny jsou nutné k tomu, aby pevný program měl přístup k neomezenému počtu registrů, protože vstupy se mění. “(Str. 73)

• Nevázané kapacity registrů versus ohraničené kapacity instrukcí stavového stroje : Takzvaná konečná část stroje má být-podle normální definice algoritmu- velmi konečná jak v počtu „stavů“ (instrukcí), tak v velikosti pokynů (jejich schopnost pojmout symboly/znaky). Jak tedy stavový stroj přesune libovolně velkou konstantu přímo do registru, např. MOVE (k, r) (Přesunout konstantu k do registru r)? Pokud jsou nutné obrovské konstanty, musí buď začít v samotných registrech, nebo je vytvořit stavový automat pomocí konečného počtu instrukcí, např. Vynásobit a přidat podprogramy pomocí INC a DEC (ale ne jejich kvazi-nekonečný počet!).

Někdy bude konstanta k vytvořena pomocí CLR (r) následovaného INC (r) opakovaným k krát - např. Pro vložení konstanty k = 3 do registru r, tj. 3 → r, takže na konci instrukce [r ] = 3: CLR (r), INC (r), INC (r), INC (r). Tento trik zmiňuje Kleene (1952) s. 223. Problém nastává, když číslo, které má být vytvořeno, vyčerpává počet instrukcí, které jsou k dispozici stroji s konečným stavem; vždy existuje větší konstanta než počet instrukcí, které má konečný automat k dispozici.

• Neomezené počty registrů versus instrukce omezeného stavového stroje : Toto je závažnější než první problém. Zejména tento problém nastává, když se pokoušíme postavit takzvaný RASP, „univerzální stroj“ (více na stroji Universal Turing ), který pomocí svého stroje s konečným stavem interpretuje „program instrukcí“ umístěný v jeho registrech- tj. stavíme to, čemu se dnes říká počítač s von Neumannovou architekturou .

Všimněte si toho, že konečný stav počítače počitadla musí vyvolat registr explicitně (přímo) svým jménem/číslem: INC (65 356) volá číslo registru „65 365“ výslovně . Pokud počet registrů překročí schopnost stroje konečného stavu je adresovat, pak registry mimo hranice budou nedostupné. Pokud například stroj s konečným stavem může dosáhnout pouze 65 536 = 2 ¹⁶ registrů, jak pak může dosáhnout 65 537?

Tak jak to budeme řešit registr za hranicemi na konečný automat? Jedním z přístupů by bylo upravit programové instrukce (ty uložené v registrech) tak, aby obsahovaly více než jeden příkaz. Ale i to může být vyčerpáno, pokud instrukce nemá (potenciálně) neomezenou velikost. Proč tedy nevyužít pouze jednu „über-instrukci“-jedno opravdu velké číslo-které obsahuje všechny do ní zakódované programové instrukce! Minsky takto řeší problém, ale Gödelovo číslování, které používá, představuje pro model velkou nepříjemnost a výsledkem není vůbec nic jako naše intuitivní představa „počítače s uloženým programem“.

Elgot a Robinson (1964) dospěli k podobnému závěru, pokud jde o RASP, který je „definitivně určen“. Skutečně může přistupovat k neomezenému počtu registrů (např. Pro načítání instrukcí z nich), ale pouze pokud RASP umožňuje „vlastní úpravu“ svých programových instrukcí a svá „data“ zakódoval do Gödelova čísla (obr. 2 s. 396) ).

V kontextu více počítačového modelu využívajícího jeho instrukci RPT (opakování) nás Minsky (1967) tantalizuje řešením problému (srov. S. 214, s. 259), ale nenabízí žádné pevné řešení. Tvrdí:

„Operace RPT obecně nemohla být instrukcí v konečné části stroje ... to by mohlo vyčerpat jakékoli konkrétní množství paměti povolené v konečné části počítače [sic, jeho jméno pro jeho modely RAM]. Operace RPT vyžadují vlastní nekonečné registry. “ (str. 214).

Nabízí nám ohraničený RPT, který společně s CLR (r) a INC (r) dokáže vypočítat jakoukoli primitivní rekurzivní funkci , a nabízí neomezený RPT citovaný výše, který hraje roli μ operátoru; společně s CLR (r) a INC (r) mohou vypočítat rekurzivní funkce mu. Nemluví však o „indirection“ ani o modelu RAM jako takovém.

Z odkazů v Hartmanisovi (1971) vyplývá, že Cook (ve svých přednáškách na UC Berkeley, 1970) upevnil pojem nepřímého adresování. Jasněji to ukazuje článek Cook and Reckhow (1973) - Cook je poradcem diplomové práce Reckhow. Hartmanisův model-velmi podobný modelu Melzakova (1961)-používá sčítání a odčítání dvou a tří registrů a dvě kopie parametrů; Cookův a Reckhowův model redukují počet parametrů (registrů vyvolaných v programových instrukcích) na jedno vyvolání pomocí akumulátoru „AC“.

Řešení v kostce: Navrhněte náš stroj / model s nespoutanou indirection  - poskytovat neomezenou „adresu“ registr, který může potenciálně pojmenovat (volat) jakýkoli zaregistrovat bez ohledu na to, kolik jich je. Aby to fungovalo, obecně platí, že neomezený registr vyžaduje schopnost vymazat a poté zvýšit (a případně snížit) potenciálně nekonečnou smyčkou. V tomto smyslu řešení představuje neomezený μ operátor, který může v případě potřeby lovit neomezeně po neomezeném řetězci registrů, dokud nenajde to, co hledá. Registr ukazatelů je přesně jako každý jiný registr s jedinou výjimkou: za okolností zvaných „nepřímé adresování“ poskytuje jeho adresu, nikoli adresní operand v TABLE stavového stroje, adresu cílového registru (včetně možná samotného) !).

Ohraničené směrování a primitivní rekurzivní funkce

Vyvarujeme-li se Minskyho přístupu jednoho čísla příšery v jednom registru a určíme, že náš model stroje bude „jako počítač“, musíme se tomuto problému indirection postavit, pokud máme počítat rekurzivní funkce (také nazývané μ-rekurzivní funkce ) - celkové i dílčí odrůdy.

Náš jednodušší pultový strojový model může provádět „ohraničenou“ formu indirekce-a tím vypočítat podtřídu primitivních rekurzivních funkcí  -pomocí primitivního rekurzivního „operátoru“ nazývaného „definice případy“ (definováno v Kleene (1952) s 229 a Boolos-Burgess-Jeffrey str. 74). Takové „ohraničené směrování“ je pracná a únavná záležitost. „Definice podle případů“ vyžaduje, aby stroj určil/rozlišil obsah registru ukazatelů pokusem, čas od času do úspěchu, porovnat tento obsah s číslem/jménem, ​​které operátor případu výslovně deklaruje. Definice podle případů tedy začíná např. Z adresy nižší hranice a pokračuje ad nauseam směrem k adrese horní hranice, která se pokouší o shodu:

Je číslo v registru N rovné 0? Pokud ne, pak se rovná 1? 2? 3? ... 65364? Pokud ne, jsme na posledním čísle 65365 a toto by mělo být lepší, jinak máme problém!

"Bounded" indirection nám nedovolí vypočítat částečné rekurzivní funkce - pro ty, které potřebujeme neomezenou indirection aka μ operátor .

Předpokládejme, že bychom mohli pokračovat na číslo 65367, a ve skutečnosti měl registr to, co jsme hledali. Pak jsme mohli úspěšně dokončit náš výpočet! Předpokládejme však, že 65367 nemá to, co jsme potřebovali. Jak daleko bychom měli pokračovat?

Aby byl čítač ekvivalentní Turingovi, musí buď použít nešťastnou metodu Minsky Gödel s jedním registrem s jedním registrem , nebo musí být rozšířen o schopnost prozkoumat konce řetězce svých registrů, v případě potřeby ad infinitum. (Neschopnost najít něco „tam venku“ definuje, co to znamená, že se algoritmus nepodaří ukončit; srov. Kleene (1952) s. 316ff Kapitola XII Částečné rekurzivní funkce , zejména s. 323-325.) Více o tom v příklad níže.

Neomezené směrování a částečné rekurzivní funkce

Pro neomezené směrování vyžadujeme změnu „hardwaru“ v našem modelu stroje. Jakmile provedeme tuto změnu, model již nebude počítačem, ale spíše strojem s náhodným přístupem.

Když je nyní zadáno např. INC, instrukce stroje konečného stavu bude muset určit, odkud pochází adresa registru zájmu. To , kde může být buď (i) pokyn státního stroje, který poskytuje explicitní označení , nebo (ii) pointer-registr , jehož obsah je adresa zájmu. Kdykoli instrukce určuje adresu registru, bude nyní také muset zadat další parametr „i/d“ - „nepřímý/přímý“. V jistém smyslu je tento nový parametr „i/d“ „přepínač“, který převrací jeden způsob, jak získat přímou adresu, jak je uvedeno v instrukci, nebo druhý způsob, jak získat nepřímou adresu z registru ukazatelů (který registr ukazatele - v některých modely každý registr může být ukazatelem - je specifikován instrukcí). Tato „vzájemně se vylučující, ale vyčerpávající volba“ je dalším příkladem „definice podle případů“ a aritmetický ekvivalent uvedený v následujícím příkladu je odvozen z definice v Kleene (1952) s. 229.

Příklad: CPY (nepřímý _zdroj , r _zdroje , přímé _určení , r _cíl )

Přiřazením kódu určete přímé adresování jako d = "0" a nepřímé adresování jako i = "1". Náš stroj pak může určit zdrojovou adresu následujícím způsobem:

i*[r _s ] + (1-i)*r _s

Předpokládejme například, že obsah registru 3 je „5“ (tj. [3] = 5) a obsah registru 4 je „2“ (tj. [4] = 2):

Příklad: CPY (1, 3, 0, 4) = CPY (nepřímý, reg 3, přímý, reg 4)

1*[3] + 0*3 = [3] = adresa registru zdroje 5

0*[4] + 1*4 = 4 = adresa registru cíle 4

Příklad: CPY (0, 3, 0, 4)

0*[3] + 1*3 = 3 = adresa registru zdroje 3

0*[4] + 1*4 = 4 = adresa registru cíle 4

Příklad: CPY (0, 3, 1, 4)

0*[3] + 1*3 = 3 = adresa registru zdroje 3

1*[4] + 0*4 = [4] = adresa registru cíle 2

Nepřímá instrukce COPY

Asi nejužitečnější z přidaných pokynů je KOPÍROVAT. Ve skutečnosti Elgot-Robinson (1964) poskytuje svým modelům P ₀ a P ' ₀ instrukce COPY a Cook-Reckhow (1973) poskytuje svému modelu založenému na akumulátoru pouze dvě nepřímé instrukce-COPY do akumulátoru nepřímo, COPY z akumulátoru nepřímo .

Mnoho instrukcí : Protože jakoukoli instrukci působící na jeden registr lze rozšířit o její nepřímé „duální“ (včetně podmíněných a bezpodmínečných skoků, viz model Elgot-Robinson), zahrnutí nepřímých instrukcí zdvojnásobí počet jednotlivých parametrů/ zaregistrujte pokyny (např. INC (d, r), INC (i, r)). Horší je, že každé dva instrukce parametru/registru budou mít 4 možné varianty, např .:

CPY (d, r _s , d, r _d ) = KOPÍROVAT přímo ze zdrojového registru přímo do cílového registru

CPY (i, r _sp , d, r _d ) = KOPÍROVAT do cílového registru nepřímo pomocí zdrojové adresy, která se nachází v registru zdrojového ukazatele r _sp .

CPY (d, r _s , i, r _dp ) = KOPÍROVAT obsah zdrojového registru nepřímo do registru pomocí cílové adresy, kterou najdete v registru cílového ukazatele r _dp .

CPY (i, r _sp , i, r _dp ) = KOPÍROVAT nepřímo obsah zdrojového registru s adresou, která se nachází v registru zdrojového ukazatele r _sp , do cílového registru s adresou, která se nachází v registru cílového ukazatele r _dp )

Podobným způsobem každá instrukce se třemi registry, která zahrnuje dva zdrojové registry r _s1 r _s2 a cílový registr r _d, bude mít za následek 8 odrůd, například přidání:

[r _s1 ] + [r _s2 ] → r _d

přinese:

• PŘIDAT (d, r _s1 , d, r _s2 , d, r _d )
• PŘIDAT (i, r _sp1 , d, r _s2 , d, r _d )
• PŘIDAT (d, r _s1 , i, r _sp2 , d, r _d )
• PŘIDAT (i, r _sp1 , i, r _sp2 , d, r _d )
• PŘIDAT (d, r _s1 , d, r _s2 , i, r _dp )
• PŘIDAT (i, r _sp1 , d, r _s2 , i, r _dp )
• PŘIDAT (d, r _s1 , i, r _sp2 , i, r _dp )
• PŘIDAT (i, r _sp1 , i, r _sp2 , i, r _dp )

Pokud označíme jeden registr jako „akumulátor“ (viz níže) a klademe důrazná omezení na různé povolené pokyny, pak můžeme značně omezit množství přímých a nepřímých operací. Musíme si však být jisti, že výsledná redukovaná sada instrukcí je dostačující, a musíme si být vědomi toho, že redukce bude na úkor více instrukcí na „významnou“ operaci.

Pojem „akumulátor A“

Historická konvence věnuje registr akumulátoru, „aritmetickému orgánu“, který doslova akumuluje své číslo během sekvence aritmetických operací:

„První část našeho aritmetického orgánu ... by měla být paralelním skladovacím orgánem, který může přijmout číslo a přidat ho k tomu, který již v něm je, který je také schopen vymazat jeho obsah a který může uložit to, co obsahuje. nazývejte takový orgán akumulátorem . Je to v zásadě v zásadě běžné v minulých i současných počítačových strojích nejrůznějších typů, např. stolní multiplikátory, standardní čítače IBM, modernější reléové stroje, ENIAC “(tučné písmo v originále: Goldstine a von Neumann , 1946; s. 98 v Bell a Newell 1971).

Akumulátor je však na úkor více instrukcí na aritmetickou „operaci“, zejména s ohledem na takzvané instrukce „čtení-modifikace-zápis“, jako je „nepřímý přírůstek obsahu registru, na který ukazuje registr r2“. „A“ označuje registr „akumulátoru“ A:

Označení	Návod		A	r2	r 378 426	Popis
			. . .	378,426	17
INCi (r2):	CPY (i, r2, d, A)		17	378,426	17	Obsah r2 ukazuje na r378,426 s obsahem „17“: zkopírujte do A
	INC (A)		18	378,426	17	Obsah vstupu A
	CPY (d, A, i, r2)		18	378,426	18	Obsah r2 ukazuje na r378,426: zkopírujte obsah A do r378,426

Pokud se budeme držet konkrétního názvu akumulátoru, např. „A“, můžeme akumulátor v pokynech naznačit, např.

INC (A) = INCA

Když však píšeme pokyny CPY bez vyvolaného akumulátoru, jsou pokyny nejednoznačné nebo musí mít prázdné parametry:

CPY (d, r2, d, A) = CPY (d, r2,,)

CPY (d, A, d, r2) = CPY (,, d, r2)

Historicky se stalo, že tyto dvě instrukce CPY získaly rozlišovací jména; žádná úmluva však neexistuje. Tradice (např. Knuthův (1973) imaginární počítač MIX ) používá dvě jména zvaná LOAD a STORE. Zde přidáváme parametr „i/d“:

LDA (d/i, r _s ) = _def CPY (d/i, r _s , d, A)

STA (d/i, r _d ) = _def CPY (d, A, d/i, r _d )

Typický model založený na akumulátoru bude mít všechny své dvě proměnné aritmetické a konstantní operace (např. ADD (A, r), SUB (A, r)) použije (i) obsah akumulátoru společně s (ii) obsahem určeného registru . Operace s jednou proměnnou (např. INC (A), DEC (A) a CLR (A)) vyžadují pouze akumulátor. Oba typy instrukcí ukládají výsledek (např. Součet, rozdíl, součin, podíl nebo zbytek) do akumulátoru.

Příklad: INCA = [A] +1 → A

Příklad: ADDA (r _s ) = [A] + [r _s ] → A

Příklad: MULA (r _s ) = [A] * [r _s ] → A

Pokud se tak rozhodneme, můžeme zkrátit mnemotechniku, protože alespoň jeden zdrojový registr a cílový registr je vždy akumulátor A. Máme tedy:

{LDA (i/d, r _s ), STA (i/d, r _d ), CLRA, INCA, DECA, ADDA (r _s ), SUBA (r _s ), MULA (r _s ), DIVA (r _s ) , atd.)

Pojem nepřímý registr adres „N“

Pokud má náš model neomezený akumulátor, můžeme svázat všechny ostatní registry? Ne, dokud nezajistíme alespoň jeden neomezený registr, ze kterého odvozujeme naše nepřímé adresy.

Minimalistický přístup je použít sám sebe (Schönhage to dělá).

Jiný přístup (Schönhage to také dělá) je deklarovat konkrétní registr jako „nepřímý registr adres“ a omezit indirection vzhledem k tomuto registru (Schonhageův model RAM0 používá jak A, tak N registry pro nepřímé i přímé instrukce). Náš nový registr opět nemá konvenční název - třeba „N“ z „iNdex“, „iNdirect“ nebo „číslo adresy“.

Pro maximální flexibilitu, jako jsme to udělali u akumulátoru A-budeme uvažovat N jen další registr podléhající přírůstku, úbytku, vymazání, testu, přímé kopii atd. Opět můžeme instrukci zmenšit na jeden parametr, který stanoví směr a například směrovost.

LDAN (i/d) = CPY (i/d, N, d, A); Akumulátor LoaD prostřednictvím registru iNdirection

STAN (i/d) = CPY (d, A, i/d, N). Uložte akumulátor přes registr iNdirection

Proč je to tak zajímavý přístup? Nejméně dva důvody:

(1) Sada instrukcí bez parametrů:

Schönhage to dělá, aby vytvořil svou instrukční sadu RAM0. Viz část níže.

(2) Redukovat RAM na Post-Turingův stroj:

Vystupujíc jako minimalisté, redukujeme všechny registry kromě akumulátoru A a indirekčního registru N, např. R = {r0, r1, r2, ...} na neomezený řetězec (velmi) ohraničených holubích děr. Nebudou dělat nic jiného, ​​než držet (velmi) ohraničená čísla, např. Osamělý bit s hodnotou {0, 1}. Stejně tak zmenšíme akumulátor na jeden bit. Omezíme jakoukoli aritmetiku na registry {A, N}, pomocí nepřímých operací natáhneme obsah registrů do akumulátoru a zapíšeme 0 nebo 1 z akumulátoru do registru:

{LDA (i, N), STA (i, N), CLR (A/N), INC (A/N), DEC (N), JZ (A/N, I _z ), JZ (I _z ), H}

Posouváme se dále a úplně eliminujeme A pomocí dvou „konstantních“ registrů nazývaných „ERASE“ a „PRINT“: [ERASE] = 0, [PRINT] = 1.

{CPY (d, ERASE, i, N), CPY (d, PRINT, i, N), CLR (N), INC (N), DEC (N), JZ (i, N, I _z ), JZ ( I _z ), H}

Přejmenujte pokyny COPY a zavolejte INC (N) = RIGHT, DEC (N) = LEFT a máme stejné pokyny jako stroj pro následné vytvrzování, plus navíc CLRN:

{ERASE, PRINT, CLRN, RIGHT, LEFT, JZ (i, N, I _z ), JZ (I _z ), H}

Turingova ekvivalence RAM s indirection

Ve výše uvedené části jsme neformálně ukázali, že RAM s neomezenou schopností přesměrování produkuje stroj Post -Turing . Post -Turingův stroj je Turingův ekvivalent, takže jsme ukázali, že RAM s indirection je Turingův ekvivalent.

Podáváme zde trochu formálnější ukázku. Začněte návrhem našeho modelu se třemi vyhrazenými registry „E“, „P“ a „N“, plus neomezenou sadou registrů 1, 2, ..., n vpravo. Registry 1, 2, ..., n budou považovány za "čtverce pásky". Registr „N“ ukazuje na „naskenovaný čtverec“, který „hlava“ aktuálně pozoruje. O „hlavě“ lze uvažovat jako o podmíněném skoku-pozorujte, že používá nepřímé adresování (srov. Elgot-Robinson str. 398). Když snižujeme nebo zvyšujeme „N“, (zdánlivá) hlava se „bude pohybovat doleva“ nebo „doprava“ po polích. Pomocí nepřímého CPY přesuneme obsah „E“ = 0 nebo „P“ = 1 na „naskenovaný čtverec“, jak ukazuje N.

Skutečnost, že naše páska je zakončena zleva, pro nás představuje menší problém: Kdykoli dojde k DOLEVĚ, naše instrukce budou muset otestovat, zda je obsah „N“ nulový; pokud ano, měli bychom nechat jeho počet na „0“ (toto je naše volba jako návrhářů - například můžeme nechat stroj/model „vyvolat událost“ podle našeho výběru).

Sada instrukcí 1 (rozšířená): {INC (N), DEC (N), CLR (N), CPY (d, r _s , i, N), JZ (i, r, z), HALT}

Následující tabulka definuje instrukce Post-Turing z hlediska jejich ekvivalentních instrukcí RAM a uvádí příklad jejich fungování. (Zdánlivé) umístění hlavy podél pásky registrů r0-r5. . . je zobrazeno zastíněno:

Mnemotechnická pomůcka	označení:			E	P	N.		r0	r1	r2	r3	r4	r5	atd.	Akce na registry	Akce na stroji konečného stavu Instrukce Registrace IR
	Start:			0	1	3					1	0
R.	že jo:	INC (N)		0	1	4					1	0			[N] +1 → N.	[IR] +1 → IR
P	tisk:	CPY (d, P, i, N)		0	1	4					1	1			[P] = 1 → [N] = r4	[IR] +1 → IR
E	vymazat:	CPY (d, E, i, N)		0	1	4					1	0			[E] = 0 → [N] = r4	[IR] +1 → IR
L	vlevo, odjet:	JZ (i, N, konec)		0	1	4					1	0			žádný	IF N = r4] = 0 PAK „konec“ → IR else [IR] +1 → IR
		DEC (N)		0	1	3					1	0			[N] -1 → N
J0 (zastavení)	jump_if_blank:	JZ (i, N, konec)		0	1	3					1	0			žádný	IF N = r3] = 0 PAK „konec“ → IR else [IR] +1 → IR
J1 (zastavení)	jump_if_mark:	JZ (i, N, zastavení)		0	1	3					1	0			N = r3] → A	IF N = r3] = 0 PAK „konec“ → IR else [IR] +1 → IR
	konec	. . . atd.		0	1	3					1	0
	Stůj:	H		0	1	3					1	0			žádný	[IR] +1 → IR

Příklad: Ohraničené směrování poskytuje stroj, který není Turingovým ekvivalentem

Během této demonstrace musíme mít na paměti, že instrukce v TABLE stroje konečného stavu jsou ohraničené , tj. Konečné :

„Kromě toho , že je algoritmus pouhou konečnou sadou pravidel, která dává posloupnost operací k řešení konkrétního typu problému, má pět důležitých funkcí [konečnost, definičnost, vstup, výstup, účinnost]“ (kurzíva, Knuth, s. 4) -7).

Problém nastává, protože registry mají explicitní „jména“ (čísla) a náš počítač musí každý vyvolat jménem, ​​aby k němu měl „přístup“.

Nepřímou CPY (i, q, d, φ) postavíme pomocí operátoru CASE. Adresa cílového registru bude upřesněna obsahem registru „q“; jakmile operátor CASE určí, co je toto číslo, CPY přímo uloží obsah registru s tímto číslem do registru „φ“. Budeme potřebovat další registr, který budeme nazývat „y“-slouží jako up-counter.

Následující text je tedy vlastně konstruktivní ukázkou nebo důkazem toho, že můžeme skutečně simulovat nepřímý CPY (i, q, d, φ) bez „hardwarové“ změny designu našeho čítače/modelu. Všimněte si však, že protože tato nepřímá CPY je "ohraničená" velikostí/rozsahem konečného stavového stroje, může RASP využívající tuto nepřímou CPY vypočítat pouze primitivní rekurzivní funkce , nikoli celou sadu rekurzivních funkcí mu .

CASE „operátor“ je popsán v Kleene (1952) (s. 229) a v Boolos-Burgess-Jeffrey (2002) (s. 74); posledně jmenovaní autoři zdůrazňují jeho užitečnost. Následující definice je pro Kleene, ale upravená tak, aby odrážela známou konstrukci „IF-THEN-ELSE“.

Operátor CASE „vrací“ přirozené číslo do φ podle toho, který „případ“ je splněn, počínaje „case_0“ a postupně procházet „case_last“; pokud není splněn žádný případ, pak se do φ vrátí číslo s názvem „výchozí“ (aka „woops“) (zde x označuje nějaký výběr parametrů, např. registr q a řetězec r0, ... rlast)):

Definice podle případů φ ( x , y):

• case_0: IF Q ₀ ( x , y) is true THEN φ ₀ ( x , y) ELSE
• case_1: IF Q ₁ ( x , y) is true THEN φ ₁ ( x , y) ELSE
• cases_2 through case_next_to_last: atd. . . . . . . . JINÝ
• case_last: IF Q _last ( x , y) is true THEN φ _last ( x , y) ELSE
• výchozí: do φ _default ( x , y)

Kleene požadují, aby „predikáty“ Q _n, které provádějí testování, byly všechny vzájemně se vylučující - „predikáty“ jsou funkce, které produkují pouze {true, false} pro výstup; Boolos-Burgess-Jeffrey přidal požadavek, aby případy byly „vyčerpávající“.

Začínáme číslem v registru q, které představuje adresu cílového registru. Ale co je toto číslo? „Predikáty“ to otestují, aby zjistili, jeden pokus za druhým: JE (q, y, z) následovaný INC (y). Jakmile je číslo explicitně identifikováno, operátor CASE přímo/explicitně zkopíruje obsah tohoto registru do φ:

Definice podle případů CPY (i, q, d, φ) = _def φ (q, r0, ..., rlast, y) =

• case_0: IF CLR (y), [q] - [y] = 0 THEN CPY (r0, φ), J (exit) ELSE
• case_1: IF INC (y), [q] = [y] = 1 THEN CPY (r1, φ), J (exit) ELSE
• case_2 through case n: IF. . . PAK . . . JINÝ
• case_n: IF INC (y), [q] = [y] = n THEN CPY (rn, φ), J (exit) ELSE
• case_n+1 to case_last: IF. . . PAK . . . JINÝ
• case_last: IF INC (y), [q] = [y] = "last" THEN CPY (rlast, φ), J (exit) ELSE
• výchozí: woops

Případ_0 (základní krok rekurze na y) vypadá takto:

• case_0 :

• CLR (y); nastavit registr y = 0
• JE (q, y, _φ0 )
• J ( případ_1 )

• _φ0: CPY (r0, φ)
• J ( výstup )

• case_1: atd.

Case_n (indukční krok) vypadá takto; pamatujte, že každá instance „n“, „n+1“, ..., „last“ musí být explicitní přirozené číslo:

• case_n :

• INC (y)
• JE (q, y, _φn )
• J ( případ_n+1 )

• _φn: CPY (rn, φ)
• J ( výstup )

• case__n+1: atd.

Case_last zastaví indukci a ohraničí operátor CASE (a tím ohraničí operátor "nepřímé kopírování"):

• case_last :

• INC (y)
• JE (q, y, _φlast )
• J ( woops )

• _φlast : CPY (rlast, φ)
• J ( výstup )

• woops: jak zvládneme pokus mimo hrací plochu?
• výstup: atd.

Pokud by CASE mohl pokračovat do nekonečna, byl by to operátor mu . Ale nemůže - „stavový registr“ jeho konečného stavového stroje dosáhl maximálního počtu (např. 65365 = 11111111,11111111 ₂ ) nebo v jeho tabulce došly instrukce; je to koneckonců konečný stroj.

Příklady modelů

Register-to-register („čtení-úprava-zápis“) modelu Cook and Reckhow (1973)

Běžně se vyskytující model Cook a Rechkow je trochu podobný modelu Malzek s ternárním registrem (psáno pomocí Knuthovy mnemotechniky-původní instrukce neměla žádnou mnemotechniku ​​kromě TRA, Read, Print).

• LOAD ( C, rd ) ; C → rd, C je libovolné celé číslo

Příklad: LOAD ( 0, 5 )vymaže registr 5.

• ADD ( rs1, rs2, rd ) ; [rs1] + [rs2] → rd, registry mohou být stejné nebo různé;

Příklad: ADD ( A, A, A )zdvojnásobí obsah registru A.

• SUB ( rs1, rs2, rd ) ; [rs1] - [rs2] → rd, registry mohou být stejné nebo různé:

Příklad: SUB ( 3, 3, 3 )vymaže registr 3.

• COPY ( i, rp, d, rd ) ; [[rp] ] → rd„Nepřímo zkopírujte obsah zdrojového registru, na který ukazuje registr ukazatele r _p, do cílového registru.
• COPY ( d, rs, i, rp ) ; [rs] → [rp]. Zkopírujte obsah zdrojového registru r _s do cílového registru, na který ukazuje registr ukazatele r _p .
• JNZ ( r, Iz ) ;Podmíněný skok, pokud [r] je kladné; tj. KDYŽ [r]> 0 POTOM přeskočte na instrukci z else pokračujte v sekvenci (Cook a Reckhow tomu říkají: „TRAnsfer control to line m if Xj> 0“)
• READ ( rd ) ;zkopírujte "vstup" do cílového registru r _d
• PRINT ( rs ) ;zkopírujte obsah zdrojového registru r _s na „výstup“.

Schönhage's RAM0 and RAM1 (1980)

Schönhage (1980) popisuje velmi primitivní atomizovaný model zvolený jako důkaz ekvivalence svého modelu ukazovacího stroje SMM :

„Aby se zabránilo jakémukoli explicitnímu adresování, má RAM0 akumulátor s obsahem z a další registr adres s aktuálním obsahem n (původně 0)“ (str. 494)

Model RAM1 : Schönhage ukazuje, jak lze jeho konstrukci použít k vytvoření běžnější, použitelné formy „nástupnické“ paměti RAM (pomocí mnemotechniky tohoto článku):

• LDA k ; k --> A , k je konstanta, explicitní číslo jako „47“
• LDA ( d, r ) ; [r] → A ; přímo načíst A
• LDA ( i, r ) ; [[r]] → A ; nepřímo zatěžovat A
• STA ( d, r ) ; [A] → r ; přímo uložit A.
• STA ( i, r ) ; [A] → [r] ; nepřímo skladovat A.
• JEA ( r, z ) ; IF [A] = [r] then Iz else continue
• INCA ; [A] + 1 --> A

Model RAM0 : Stroj RAM0 společnosti Schönhage má 6 instrukcí označených jediným písmenem (6. „C xxx“ jako by zahrnovalo „přeskočení dalšího parametru“. Schönhage označil akumulátor jako „z“, „N“ s „n“ atd. Spíše než Schönhageovy mnemotechnické pomůcky použijeme výše uvedené mnemotechnické pomůcky.

• (Z), CLRA: 0 → A
• (A), INCA: [A] +1 → A
• (N), CPYAN: [A] → N
• (A), LDAA: [[A]] → A ; obsah A bodů k registraci adresy; vložte obsah registru do A
• (S), STAN: [A] → [N] ; obsah N bodů k registrační adrese; vložte obsah A do registru, na který ukazuje N.
• (C), JAZ ( z ): [A] = 0 then go to Iz ; nejednoznačné v jeho léčbě

Indirection pochází (i) z CPYAN (kopírování/přenos obsahu A do N) pracujícího s store_A_via_N STAN a z (ii) zvláštní instrukce indirection LDAA ( [[A]] → [A] ).

Poznámky pod čarou

Konečné vs neomezené

Definiční skutečnost, že jakýkoli druh čítače bez neomezeného registru-registr „adresy“ musí specifikovat registr „r“ podle názvu, naznačuje, že model vyžaduje, aby „r“ bylo konečné , ačkoli je „neomezené“ v tom smyslu, že model neznamená žádný horní limit pro počet registrů nezbytných k plnění jeho úkolů. Například nepožadujeme r <83 617 563 821 029 283 746 ani r <2^1 000 001 atd.

Náš model tedy může "rozšířit" počet registrů, pokud je to nutné k provedení určitého výpočtu. To však znamená, že jakékoli číslo, na které se model rozšíří, musí být konečné  - musí být indexovatelné s přirozeným číslem: ω není možnost .

Můžeme uniknout tomuto omezení tím, že poskytneme neomezený registr, který poskytne adresu registru, která určuje nepřímou adresu.

Viz také

• Skutečná RAM
• Transdichotomický model

externí odkazy

• Emulátor stroje s náhodným přístupem
• Emulátor stroje s náhodným přístupem
• Emulátor stroje s náhodným přístupem

Reference

Až na několik výjimek jsou tyto odkazy stejné jako u stroje Register .

• • Goldstine, Herman H. a von Neumann, John, „Planning and Coding of the Problems for an Electronic Computing Instrument“, Rep. 1947, Institute for Advanced Study , Princeton. Přetištěno na s. 92–119 v Bell, C. Gordon a Newell, Allen (1971), Computer Structures: Readings and examples , McGraw-Hill Book Company, New York. ISBN  0-07-004357-4 }.
• George Boolos , John P. Burgess , Richard Jeffrey (2002), Computability and Logic: Fourth Edition , Cambridge University Press, Cambridge, England. Původní text Boolos-Jeffrey byl Burgessem značně revidován: pokročilejší než úvodní učebnice. „Abacus machine“ model je rozsáhle vyvinut v kapitole 5 Abacus Computability ; je to jeden ze tří modelů, které byly důkladně zpracovány a porovnány-Turingův stroj (stále v původní Boolosově 4-tuplové formě) a rekurze ostatních dvou.
• Arthur Burks , Herman Goldstine , John von Neumann (1946), Předběžná diskuse o logickém návrhu elektronického výpočetního nástroje , přetištěný str. 92ff v Gordon Bell a Allen Newell (1971), Počítačové struktury: Čtení a příklady , mcGraw-Hill Book Společnost, New York. ISBN  0-07-004357-4 .
• Stephen A. Cook a Robert A. Reckhow (1973), Time-bounded random access machines , Journal of Computer Systems Science 7 (4): 354-375.
• Martin Davis (1958), Computability & Unsolvability , McGraw-Hill Book Company, Inc. New York.
• Calvin Elgot a Abraham Robinson (1964), Random-Access Stored-Program Machines, an Approach to Programming Languages , Journal of the Association for Computing Machinery, Vol. 11, č. 4 (říjen 1964), s. 365–399.
• J. Hartmanis (1971), „Computational Complexity of Random Access Stored Program Machines,“ Mathematical Systems Theory 5, 3 (1971) str. 232–245.
• John Hopcroft , Jeffrey Ullman (1979). Úvod do teorie automatů, jazyků a výpočetní techniky , 1. vydání, Reading Mass: Addison-Wesley. ISBN  0-201-02988-X . Složitá kniha soustředěná kolem problémů strojové interpretace „jazyků“, NP-úplnosti atd.
• Stephen Kleene (1952), Úvod do metamatematiky , North-Holland Publishing Company, Amsterdam, Nizozemsko. ISBN  0-7204-2103-9 .
• Donald Knuth (1968), The Art of Computer Programming , Second Edition 1973, Addison-Wesley, Reading, Massachusetts. Viz strany 462–463, kde definuje „nový druh abstraktního stroje nebo„ automatu “, který se zabývá propojenými strukturami.
• Joachim Lambek (1961, obdržel 15. června 1961), How to Program an Infinite Abacus , Mathematical Bulletin, sv. 4, č. 3. Září 1961 strany 295-302. Lambek ve své příloze II navrhuje „formální definici„ programu “. Odkazuje na Melzak (1961) a Kleene (1952) Úvod do metamatematiky .
• ZA Melzak (1961, přijato 15. května 1961), Neformální aritmetický přístup k počitatelnosti a počítání , Kanadský matematický bulletin , sv. 4, č. 3. Září 1961, strany 279-293. Melzak nenabízí žádné reference, ale uznává „přínos rozhovorů s dr. R. Hammingem, D. McIlroyem a V. Vyssotsem z Bell Bell Laboratory a s Dr. H. Wangem z Oxfordské univerzity“.
• Marvin Minsky (1961). "Rekurzivní neřešitelnost Postova problému 'Tagu' a dalších témat v teorii Turingových strojů". Annals of Mathematics . The Annals of Mathematics, sv. 74, č. 3. 74 (3): 437–455. doi : 10,2307/1970290 . JSTOR  1970290 .
• Marvin Minsky (1967). Výpočet: Konečné a nekonečné stroje (1. vyd.). Englewood Cliffs, New Jersey: Prentice-Hall, Inc.Zejména viz kapitola 11: Modely podobné digitálním počítačům a kapitola 14: Velmi jednoduché základy pro výpočetní schopnost . V předchozí kapitole definuje „Programovací stroje“ a v další kapitole pojednává o „Univerzálních programových strojích se dvěma registry“ a „... s jedním registrem“ atd.
• John C. Shepherdson a HE Sturgis (1961) obdrželi prosinec 1961 Computability of Recursive Functions , Journal of the Association of Computing Machinery (JACM) 10: 217-255, 1963. Mimořádně hodnotný referenční dokument. V dodatku A autoři citují 4 další s odkazem na „Minimalitu instrukcí použitých v 4.1: Porovnání s podobnými systémy“.

• Kaphengst, Heinz, Eine Abstrakte programmgesteuerte Rechenmaschine ' , Zeitschrift fur mathematische Logik und Grundlagen der Mathematik: 5 (1959), 366-379.
• Ershov, AP Na algoritmy operátora , (rusky) Dok. Akad. Nauk 122 (1958), 967-970. Anglický překlad, Automat. Expres 1 (1959), 20-23.
• Péter, Rózsa Graphschemata und rekurzivní Funktionen , Dialectica 12 (1958), 373.
• Hermes, Hans Die Universalität programmgesteuerter Rechenmaschinen. Math.-Phys. Semsterberichte (Göttingen) 4 (1954), 42-53.

• Arnold Schönhage (1980), Storage Modification Machines , Society for Industrial and Applied Mathematics, SIAM J. Comput. Sv. 9, č. 3, srpen 1980. Kde Schōnhage ukazuje ekvivalenci svého SMM s „nástupnickou RAM“ (Random Access Machine) atd. Resp. Storage Modification Machines , in Theoretical Computer Science (1979), s. 36–37
• Peter van Emde Boas , „Modely strojů a simulace“ s. 3–66, in: Jan van Leeuwen , ed. Příručka teoretické informatiky. Svazek A: Algoritmy a složitost , The MIT PRESS/Elsevier, 1990. ISBN  0-444-88071-2 (svazek A). QA 76.H279 1990. Van Emde Boasovo zacházení se SMM se objevuje na s. 32–35. Tato léčba vyjasňuje Schōnhage 1980 - těsně následuje, ale mírně rozšiřuje léčbu Schōnhage. K účinnému porozumění mohou být zapotřebí oba odkazy.
• Hao Wang (1957), Varianta Turingovy teorie počítačových strojů , JACM (Journal of the Association for Computing Machinery) 4; 63-92. Prezentováno na schůzi spolku, 23. – 25. Června 1954.