Slumpmässig åtkomstmaskin - Random-access machine

Inom datavetenskap är slumpmässig åtkomstmaskin ( RAM ) en abstrakt maskin i den allmänna klassen av registermaskiner . RAM -minnet är mycket likt räknemaskinen men med den extra förmågan att "indirekt adressera" dess register. Precis som motmaskinen har RAM-minnet sina instruktioner i finit-state-delen av maskinen (den så kallade Harvard-arkitekturen ).

RAM-motsvarigheten till den universella Turingmaskinen-  med dess program i registren såväl som dess data-kallas för slumpmässig åtkomst lagrad programmaskin eller RASP. Det är ett exempel på den så kallade von Neumann-arkitekturen och ligger närmast det vanliga begreppet dator .

Tillsammans med Turing maskin och kontramaskinmodeller , är RAM och RASP modeller som används för beräkningskomplexitet analys . Van Emde Boas (1990) kallar dessa tre plus pekarmaskiner för "sekventiella maskin" -modeller, för att skilja dem från " parallell maskin för slumpmässig åtkomst ".

Introduktion till modellen

Konceptet med en slumpmässig åtkomstmaskin (RAM) börjar med den enklaste modellen av alla, den så kallade motmaskinmodellen . Två tillägg flyttar dock bort den från diskmaskinen. Den första förbättrar maskinen med bekvämligheten av indirekt adressering; den andra flyttar modellen mot den mer konventionella ackumulatorbaserade datorn med tillägg av ett eller flera extra (dedikerade) register, varav den vanligaste kallas "ackumulator".

Formell definition

En slumpmässig åtkomstmaskin (RAM) är en abstrakt beräkningsmaskinmodell identisk med en räknemaskin med flera register med tillägg av indirekt adressering. Efter en bedömning av en instruktion från dess ändliga maskins TABELL, härleder maskinen ett "mål" -registers adress antingen (i) direkt från själva instruktionen, eller (ii) indirekt från innehållet (t.ex. nummer, etikett) på "pekar" -register som anges i instruktionen.

Per definition: Ett register är en plats med både en adress (en unik, urskiljbar beteckning/lokalisering som motsvarar ett naturligt tal) och ett innehåll  - ett enda naturligt nummer. För precision kommer vi att använda den kvasi-formella symboliken från Boolos-Burgess-Jeffrey (2002) för att specificera ett register, dess innehåll och en operation på ett register:

  • [r] betyder "innehållet i registret med adressen r". Etiketten "r" här är en "variabel" som kan fyllas med ett naturligt tal eller en bokstav (t.ex. "A") eller ett namn.
  • → betyder "kopiera/sätta in i", eller "ersätter", men utan att källan förstörs
Exempel: [3] +1 → 3; betyder "Innehållet i källregistret med adressen" 3 ", plus 1, sätts in i destinationsregistret med adressen" 3 "(här är källan och destinationen samma plats). Om [3] = 37, det vill säga innehållet i register 3 är siffran "37", då kommer 37+1 = 38 att sättas in i register 3.
Exempel: [3] → 5; betyder "Innehållet i källregistret med adressen" 3 "sätts in i destinationsregistret med adressen" 5 ". Om [3] = 38, det vill säga innehållet i register 3 är talet 38, kommer detta nummer att sättas in i register 5. Innehållet i register 3 störs inte av denna operation, så [3] fortsätter att vara 38, nu samma som [5].

Definition: En direkt instruktion är en som anger i själva instruktionen adressen till källan eller destinationsregistret vars innehåll kommer att bli föremål för instruktionen. Definition: En indirekt instruktion är en som anger ett "pekarregister", vars innehåll är adressen till ett "mål" -register. Målregistret kan antingen vara en källa eller en destination (de olika COPY -instruktionerna ger exempel på detta). Ett register kan adressera sig indirekt.

För brist på en standard/konvention kommer denna artikel att specificera "direkt/indirekt", förkortad som "d/i", som en parameter (eller parametrar) i instruktionen:
Exempel: KOPIERA ( d , A, i , N) betyder direkt d få källregisterets adress (register "A") från själva instruktionen men indirekt får jag destinationsadressen från pekarregister N. Antag [N] = 3, då är register 3 destinationen och instruktionen gör följande: [A] → 3.

Definition: Innehållet i källregistret används av instruktionen. Källregisterets adress kan specificeras antingen (i) direkt av instruktionen, eller (ii) indirekt av pekarregistret som anges av instruktionen.

Definition: Innehållet i pekarregistret är adressen till "mål" -registret.

Definition: Innehållet i pekarregistret pekar på målregistret  - "målet" kan antingen vara en källa eller ett destinationsregister.

Definition: Destinationsregistret är där instruktionen deponerar sitt resultat. Källregisterets adress kan specificeras antingen (i) direkt av instruktionen, eller (ii) indirekt av pekarregistret som anges av instruktionen. Käll- och destinationsregistren kan vara ett.

Uppfriskning: Motmaskinmodellen

Melzak (1961) ger en enkel visualisering av en räknemaskin: dess "register" är hål i marken, och dessa hål rymmer småsten. Enligt en instruktion lägger "datorn" (person eller maskin) in i och ut ur dessa hål (INCrements) eller tar bort (DECrements) en enda sten. Vid behov kommer ytterligare småsten från, och överflödiga stenar går tillbaka till en oändlig mängd; om hålet är för litet för att rymma småstenen gräver "datorn" hålet större.
Minsky (1961) och Hopcroft-Ullman 1979 (s. 171) erbjuder visualisering av en multi-band Turing-maskin med lika många vänsterändade band som "register". Varje tejps längd är obegränsad till höger och varje ruta är tom förutom den vänstra änden, som är markerad. Det avstånd av en tejp på "huvud" från dess vänstra ände, mätt i antal tape-rutor, representerar det naturliga talet i "registret". För att minska antalet kvadrater rör sig tejphuvudet åt vänster; ÖKAR den rör sig rätt. Det finns ingen anledning att skriva ut eller radera märken på bandet; de enda villkorliga instruktionerna är att kontrollera om huvudet är i vänster ände, genom att testa ett vänster-märke med en "Hoppa-om-märkt instruktion".
Följande instruktion "mnemonics" t.ex. "CLR (r)" är godtycklig; det finns ingen standard.

Det register Maskinen har ett minne utanför sitt finite-state machine - en obegränsad (CF: fotnot | kvantifierbart och obegränsad) samling av diskreta och unikt märkta platser med obegränsad kapacitet, som kallas "register". Dessa register innehåller endast naturliga tal (noll och de positiva heltalen). Enligt en lista över sekventiella instruktioner i finit -tillståndsmaskinens TABELL fungerar några (t.ex. 2) typer av primitiva operationer på innehållet i dessa "register". Slutligen finns ett villkorligt uttryck i form av en IF-THEN-ELSE tillgängligt för att testa innehållet i ett eller två register och "förgrena/hoppa" den slutliga tillståndsmaskinen ur standardinstruktion-sekvensen.

Basmodell 1 : Modellen närmast Minskys (1961) visualisering och Lambek (1961):

  • {Öka innehållet i register r, DECrement innehåll i register r, OM innehållet i register r är noll DÅ Hoppa till instruktion I z ELSE fortsätt till nästa instruktion}:
Instruktion Mnemonic Åtgärd angående registret "r" Åtgärd på finite state -maskinens instruktionsregister, IR
Ökning INC (r) [r] + 1 → r [IR] + 1 → IR
Minskning DEC (r) [r] - 1 → r [IR] + 1 → IR
Hoppa om noll JZ (r, z) ingen OM [r] = 0 DÅ z → IR ELLER [IR] + 1 → IR
Stanna H ingen [IR] → IR

Basmodell 2 : "efterträdarens" modell (uppkallad efter efterföljarfunktionen för Peano -axiomen ):

  • {Öka innehållet i register r, CLeaR innehållet i register r, OM innehållet i register r j Lika med innehållet i register r k DÅ Hoppa till instruktion I z ELSE gå till nästa instruktion}
Instruktion Mnemonic Åtgärd angående registret "r" Åtgärd på finite state -maskinens instruktionsregister, IR
Klar CLR (r) 0 → r [IR] + 1 → IR
Ökning INC (r) [r] + 1 → r [IR] + 1 → IR
Hoppa om lika JE (r1, r2, z) ingen OM [r1] = [r2] DÅ z → IR ELLER [IR] + 1 → IR
Stanna H ingen [IR] → IR

Basmodell 3 : Används av Elgot-Robinson (1964) i deras undersökning av begränsade och obegränsade RASP: er "efterträdarens" modell med COPY i stället för CLEAR:

  • {Inkrementera innehållet i registret r, kopiera innehållet i register r j för att registrera r k , IF innehållet i registret r j är lika med innehållet i registret r k sedan Hoppa till instruktionen I z ELSE goto till nästa instruktion}
Instruktion Mnemonic Åtgärd angående registret "r" Åtgärd på finite state -maskinens instruktionsregister, IR
KOPIERA KOPIERA (r1, r2) [r1] → r2 [IR] + 1 → IR
Ökning INC (r) [r] + 1 → r [IR] + 1 → IR
Hoppa om lika JE (r1, r2, z) ingen OM [r1] = [r2] DÅ z → IR ELLER [IR] + 1 → IR
Stanna H ingen [IR] → IR

Skapa "bekvämlighetsinstruktioner" från basuppsättningarna

De tre basuppsättningarna 1, 2 eller 3 ovan är likvärdiga i den meningen att man kan skapa instruktioner för en uppsättning med hjälp av instruktionerna från en annan uppsättning (en intressant övning: en ledtråd från Minsky (1967) - förklara ett reserverat register, t.ex. ring det "0" (eller Z för "noll" eller E för "radera") för att innehålla talet 0). Valet av modell beror på vilken författare som är lättast att använda i en demonstration, eller ett bevis, etc.

Dessutom kan vi från basuppsättningar 1, 2 eller 3 skapa vilken som helst av de primitiva rekursiva funktionerna (jfr Minsky (1967), Boolos-Burgess-Jeffrey (2002)). (Hur man kastar nätet bredare för att fånga de totala och partiella mu rekursiva funktionerna kommer att diskuteras i samband med indirekt adressering). Att bygga de primitiva rekursiva funktionerna är dock svårt eftersom instruktionsuppsättningarna är så ... primitiva (små). En lösning är att utöka en viss uppsättning med "bekvämlighetsinstruktioner" från en annan uppsättning:

Dessa kommer inte att vara subrutiner i konventionell mening utan snarare block av instruktioner som skapats från basuppsättningen och ges en mnemonic. I formell bemärkelse, för att använda dessa block måste vi antingen (i) "expandera" dem till deras basinstruktion-ekvivalenter-de kommer att kräva användning av tillfälliga eller "extra" register så modellen måste ta hänsyn till detta, eller ( ii) designa våra maskiner/modeller med instruktionerna 'inbyggda'.
Exempel: Basuppsättning 1. För att skapa CLR (r) använd instruktionsblocket för att räkna ner registret r till noll. Observera användningen av ledtråden ovan:
  • CLR (r) = ekv
  • loop : JZ (r, exit )
  • DEC (r)
  • JZ (0, loop )
  • utgång : etc.

Återigen, allt detta är endast för enkelhets skull; inget av detta ökar modellens inneboende kraft.

Till exempel: den mest utökade uppsättningen skulle innehålla varje unik instruktion från de tre uppsättningarna, plus ovillkorligt hopp J (z) dvs:

  • {CLR (r), DEC (r), INC (r), CPY (r s , r d ), JZ (r, z), JE (r j , r k , z), J (z)}

De flesta författare väljer det ena eller det andra av de villkorliga hoppen, t.ex. Shepherdson-Sturgis (1963) använder ovanstående uppsättning minus JE (för att vara helt korrekt använder de JNZ-Jump if Not Zero istället för JZ; ännu en möjlig bekvämlighetsinstruktion).

Den "indirekta" operationen

Exempel på indirekt adressering

I vårt dagliga liv är begreppet "indirekt operation" inte ovanligt.

Exempel: En skattjakt.
På plats "Tom _ & _ Becky's_cave_in_pirate_chest" kommer vi att hitta en karta som leder oss till "skatten":
(1) Vi går till platsen "Tom _ & _ Beckys_cave ..." och gräver runt tills vi hittar en trälåda
(2) Inuti rutan finns en karta till skattens plats: "under_Thatcher's_front_porch"
(3) Vi går till platsen "under_Thatchers_front_porch", hamrar bort betongen och upptäcker "skatten": en säck med rostiga dörrknoppar.

Indirection anger en plats som identifierats som piratkistan i "Tom _ & _ Becky's_cave ..." som fungerar som en pekare till någon annan plats (inklusive sig själv): dess innehåll (skattkartan) ger "adressen" till målplatsen "under_Thatcher 's_front_porch "där den verkliga handlingen sker.

Varför behovet av en indirekt operation: Två stora problem med motmaskinmodellen

I det följande måste man komma ihåg att dessa modeller är abstrakta modeller med två grundläggande skillnader från allt fysiskt verkligt: ​​obegränsat antal register var och en med obegränsad kapacitet. Problemet uppträder mest dramatiskt när man försöker använda en motmaskinsmodell för att bygga en RASP som är Turing-ekvivalent och därmed beräkna någon partiell mu-rekursiv funktion :

  • Melzak (1961) lade indirekt till sin "hål-och-sten" -modell så att hans modell kunde modifiera sig själv med en "beräknad goto" och ger två exempel på dess användning ("Decimal representation i skalan d" och "Sortera efter magnitude ", om dessa används i hans bevis på att modellen är Turing -ekvivalent är oklart eftersom" själva programmet lämnas till läsaren som en övning "(s. 292)). Minsky (1961, 1967) kunde visa att med lämplig (men svåranvänd) Gödel-nummerkodning behöver registermodellen inte vara indirekt för att vara Turing-ekvivalent; men det behövde minst ett obegränsat register. Som nämnts nedan, tipsar Minsky (1967) om problemet med en RASP men erbjuder ingen lösning. Elgot och Robinson (1964) bevisade att deras RASP -modell P 0  - den har ingen indirekt förmåga - inte kan beräkna alla "rekursiva sekventiella funktioner" (sådana som har parametrar av godtycklig längd) om den inte har förmågan att ändra sina egna instruktioner, men den kan via Gödel-nummer om den gör det (s. 395-397; i synnerhet figur 2 och fotnot s. 395). Å andra sidan kan deras RASP-modell P ' 0 utrustad med ett "indexregister" (indirekt adressering) beräkna alla "partiella rekursiva sekventiella funktioner" (mu-rekursiva funktioner) (s. 397-398).
Cook and Reckhow (1973) säger det kortfattat:
De indirekta instruktionerna är nödvändiga för att ett fast program ska få åtkomst till ett obegränsat antal register eftersom ingångarna varierar. "(S 73)
  • Obegränsade kapaciteter hos register kontra begränsade kapaciteter för tillståndsmaskininstruktioner : Den så kallade finite state-delen av maskinen är tänkt att vara-med normal definition av algoritm- mycket begränsad både i antalet "tillstånd" (instruktioner) och instruktionernas storlek (deras kapacitet att hålla symboler/tecken). Så hur flyttar en tillståndsmaskin en godtyckligt stor konstant direkt in i ett register, t.ex. MOVE (k, r) (Flytta konstant k för att registrera r)? Om enorma konstanter är nödvändiga måste de antingen börja i registren själva eller skapas av statsmaskinen med ett begränsat antal instruktioner, t.ex. multiplicera och lägga till underrutiner med INC och DEC (men inte ett kvasi-oändligt antal av dessa!).
Ibland skapas konstanten k med hjälp av CLR (r) följt av INC (r) upprepade k gånger - t.ex. för att sätta konstanten k = 3 i registret r, dvs 3 → r, så i slutet av instruktionen [r ] = 3: CLR (r), INC (r), INC (r), INC (r). Detta trick nämns av Kleene (1952) sid. 223. Problemet uppstår när numret som ska skapas tar slut på antalet instruktioner som finns tillgängliga för den slutliga tillståndsmaskinen; det finns alltid en större konstant än antalet instruktioner som finns tillgängliga för den slutliga tillståndsmaskinen.
  • Obegränsat antal register kontra begränsade instruktioner för tillståndsmaskin : Detta är allvarligare än det första problemet. I synnerhet uppstår detta problem när vi försöker bygga en så kallad RASP, en "universalmaskin" (se mer på Universal Turing-maskin ) som använder sin finita-tillståndsmaskin för att tolka ett "instruktionsprogram" som finns i dess register- dvs vi bygger det som idag kallas en dator med von Neumann -arkitekturen .
Observera att räknemaskinens finita tillståndsmaskin måste anropa ett register uttryckligen (direkt) med sitt namn/nummer: INC (65,356) ropar ut registreringsnummer "65,365" uttryckligen . Om antalet register överstiger förmågan hos finite state -maskinen att ta itu med dem kommer register utanför gränserna att inte nås. Till exempel, om den slutliga tillståndsmaskinen bara kan nå 65 536 = 2 16 register, hur kan den då nå 65 537: e?

Så hur gör vi ta itu med ett register bortom gränserna för den finita tillståndsmaskinen? Ett tillvägagångssätt skulle vara att ändra programinstruktionerna (de som är lagrade i registren) så att de innehåller mer än ett kommando. Men även detta kan uttömmas om inte en instruktion är av (potentiellt) obegränsad storlek. Så varför inte använda bara en "über-instruktion"-ett riktigt riktigt stort nummer-som innehåller alla programinstruktioner som är kodade i den! Så här löser Minsky problemet, men Gödel -numreringen han använder representerar en stor olägenhet för modellen, och resultatet är ingenting alls som vår intuitiva uppfattning om en "lagrad programdator".

Elgot och Robinson (1964) kommer till en liknande slutsats med avseende på en RASP som är "slutligt bestämd". Det kan faktiskt komma åt ett obegränsat antal register (t.ex. för att hämta instruktioner från dem) men bara om RASP tillåter "självmodifiering" av sina programinstruktioner och har kodat sina "data" i ett Gödel -nummer (Fig. 2 s. 396 ).

I samband med en mer datorliknande modell som använder sin RPT (upprepa) instruktion, lockar Minsky (1967) oss med en lösning på problemet (jfr s. 214, s. 259) men erbjuder ingen fast upplösning. Han hävdar:

"I allmänhet kan en RPT-operation inte vara en instruktion i maskinens ändliga tillstånd ... detta kan ta ut någon speciell mängd lagringsutrymme som är tillåten i den ändliga delen av datorn [sic, hans namn för hans RAM-modeller]. RPT -operationer kräver oändliga egna register. " (s 214).

Han erbjuder oss en begränsad RPT som tillsammans med CLR (r) och INC (r) kan beräkna alla primitiva rekursiva funktioner , och han erbjuder den obegränsade RPT som citeras ovan som spelar rollen som μ -operatör; den tillsammans med CLR (r) och INC (r) kan beräkna mu rekursiva funktioner. Men han diskuterar inte "indirection" eller RAM -modellen i sig.

Av referenserna i Hartmanis (1971) framgår att Cook (i sina föreläsningsanteckningar vid UC Berkeley, 1970) har bekräftat uppfattningen om indirekt adressering. Detta blir tydligare i tidningen Cook and Reckhow (1973) - Cook är Reckhows masteruppsatsrådgivare. Hartmanis modell-ganska lik Melzaks (1961) modell-använder additions och subtraheringar från två och tre register och två parameterkopior; Cook och Reckhows modell reducerar antalet parametrar (register som ropas upp i programinstruktionerna) till ett utrop genom att använda en ackumulator "AC".

Lösningen i ett nötskal: Utforma vår maskin/modell med obegränsad indirekt  - ge ett obegränsat "adress" -register som potentiellt kan namnge (ropa ut) vilket register som helst, oavsett hur många det finns. För att detta ska fungera krävs i allmänhet det obegränsade registret en förmåga att rensas och sedan ökas (och eventuellt minskas) med en potentiellt oändlig slinga. I denna mening representerar lösningen den obegränsade μ -operatören som vid behov kan jaga oändligt längs den obegränsade registret tills den hittar det den letar efter. Pekarregistret är precis som alla andra register med ett undantag: under de omständigheter som kallas "indirekt adressering" tillhandahåller det dess innehåll, snarare än adressoperanden i tillståndsmaskinens TABELL, för att vara målregistret (inklusive eventuellt sig själv !).

Gränsad indirektion och de primitiva rekursiva funktionerna

Om vi ​​undviker Minsky-metoden för ett monsternummer i ett register och anger att vår maskinmodell kommer att vara "som en dator" måste vi konfrontera detta problem med indirektion om vi ska beräkna de rekursiva funktionerna (kallas även μ-rekursiva funktioner ) - både totala och delvisa sorter.

Vår enklare motmaskinmodell kan göra en "begränsad" form av indirekt-och därmed beräkna underklassen av primitiva rekursiva funktioner-  genom att använda en primitiv rekursiv "operatör" som kallas "definition av fall" (definierad i Kleene (1952) s . 229 och Boolos-Burgess-Jeffrey s. 74). En sådan "begränsad inriktning" är en mödosam, tråkig affär. "Definition efter fall" kräver att maskinen bestämmer/urskiljer innehållet i pekarregistret genom att försöka matcha detta innehåll mot ett nummer/namn som ärendeoperatören uttryckligen deklarerar. Således börjar definitionen av fall från t.ex. den nedre gränsadressen och fortsätter ad nauseam mot den övre gränsadressen som försöker göra en matchning:

Är talet i register N lika med 0? Om inte då är det lika med 1? 2? 3? ... 65364? Om inte så är vi på sista siffran 65365 och det är bättre att ha det, annars har vi ett problem!

"Gränsad" indirektion tillåter oss inte att beräkna de partiella rekursiva funktionerna - för dem vi behöver obegränsad indirektion aka μ -operatören .

Antag att vi hade kunnat fortsätta till nummer 65367, och i själva verket hade det registret det vi letade efter. Då hade vi kunnat slutföra vår beräkning framgångsrikt! Men antar att 65367 inte hade det vi behövde. Hur långt ska vi fortsätta att gå?

För att vara Turing-ekvivalent måste räknemaskinen antingen använda den olyckliga metoden Minsky Gödel-nummer , eller förstärkas med en förmåga att utforska ändarna på dess registersträng, ad infinitum om det behövs. (Ett misslyckande med att hitta något "där ute" definierar vad det innebär för en algoritm att misslyckas med att avsluta; se Kleene (1952) s. 316ff Kapitel XII Partiella rekursiva funktioner , särskilt s. 323-325.) Se mer om detta i exemplet nedan.

Obegränsad indirektion och de partiella rekursiva funktionerna

För obegränsad inriktning kräver vi en "hårdvara" -ändring i vår maskinmodell. När vi väl gjort denna förändring är modellen inte längre en räknemaskin, utan snarare en slumpmässig åtkomstmaskin.

När t.ex. INC är specificerat måste finite state -maskinens instruktion ange var adressen till intresseboken kommer från. Detta där kan vara antingen (i) tillståndsmaskinen instruktion som ger en uttrycklig etikett , eller (ii) den pekare-registret vars innehåll är adressen av intresse. Närhelst en instruktion anger en registeradress måste den nu också ange en ytterligare parameter "i/d" - "indirekt/direkt". På ett sätt är denna nya "i/d" -parameter en "switch" som vänder på ett sätt för att få direktadressen enligt specifikationen i instruktionen eller det andra sättet att få den indirekta adressen från pekarregistret (vilket pekarregister - i vissa modeller kan varje register vara ett pekarregister - specificeras av instruktionen). Detta "ömsesidigt uteslutande men uttömmande val" är ännu ett exempel på "definition efter fall", och den aritmetiska motsvarigheten som visas i exemplet nedan härleds från definitionen i Kleene (1952) s. 229.

Exempel: CPY (indirekt källa , r källa , direkt destination , r destination )
Tilldela en kod för att ange direktadressering som d = "0" och indirekt adressering som i = "1". Då kan vår maskin bestämma källadressen enligt följande:
i*[r s ] + (1-i)*r s
Anta till exempel att innehållet i register 3 är "5" (dvs [3] = 5) och innehållet i register 4 är "2" (dvs [4] = 2):
Exempel: CPY (1, 3, 0, 4) = CPY (indirekt, reg 3, direkt, reg 4)
1*[3] + 0*3 = [3] = källregistreringsadress 5
0*[4] + 1*4 = 4 = destinationsregistreringsadress 4
Exempel: CPY (0, 3, 0, 4)
0*[3] + 1*3 = 3 = källregistreringsadress 3
0*[4] + 1*4 = 4 = destinationsregistreringsadress 4
Exempel: CPY (0, 3, 1, 4)
0*[3] + 1*3 = 3 = källregistreringsadress 3
1*[4] + 0*4 = [4] = destinationsregistreringsadress 2

Den indirekta COPY -instruktionen

Förmodligen den mest användbara av de tillagda instruktionerna är KOPIERA. Elgot-Robinson (1964) förser sina modeller P 0 och P ' 0 med COPY-instruktionerna, och Cook-Reckhow (1973) förser sin ackumulatorbaserade modell med endast två indirekta instruktioner-KOPI till ackumulator indirekt, KOPI från ackumulator indirekt .

En uppsjö av instruktioner : Eftersom all instruktion som verkar på ett enda register kan förstärkas med dess indirekta "dubbla" (inklusive villkorliga och ovillkorliga hopp, jfr Elgot-Robinson-modellen), kommer införandet av indirekta instruktioner att fördubbla antalet enskilda parametrar/ registrera instruktioner (t.ex. INC (d, r), INC (i, r)). Ännu värre, varannan parameter/registerinstruktion kommer att ha fyra möjliga sorter, t.ex.

CPY (d, r s , d, r d ) = KOPIERA direkt från källregistret direkt till destinationsregistret
CPY (i, r sp , d, r d ) = KOPIERA till destinationsregistret indirekt med hjälp av källadressen som finns i källpekarregistret r sp .
CPY (d, r s , i, r dp ) = KOPIERA innehållet i källregistret indirekt i registret med hjälp av destinationsadress som finns i destinationspekarregistret r dp .
CPY (i, r sp , i, r dp ) = KOPIERA indirekt innehållet i källregistret med adress som finns i källpekarregistret r sp , i destinationsregistret med adress som finns i destinationspekarregistret r dp )

På liknande sätt kommer varje treregisterinstruktion som involverar två källregister r s1 r s2 och ett destinationsregister r d att resultera i 8 sorter, till exempel tillägget:

[r s1 ] + [r s2 ] → r d

Kommer att ge:

  • ADD (d, r s1 , d, r s2 , d, r d )
  • ADD (i, r sp1 , d, r s2 , d, r d )
  • ADD (d, r s1 , i, r sp2 , d, r d )
  • ADD (i, r sp1 , i, r sp2 , d, r d )
  • ADD (d, r s1 , d, r s2 , i, r dp )
  • ADD (i, r sp1 , d, r s2 , i, r dp )
  • ADD (d, r s1 , i, r sp2 , i, r dp )
  • ADD (i, r sp1 , i, r sp2 , i, r dp )

Om vi ​​utser ett register som "ackumulator" (se nedan) och sätter starka restriktioner på de olika tillåtna instruktionerna kan vi kraftigt reducera mängden direkta och indirekta operationer. Man måste dock vara säker på att den resulterande reducerade instruktionsuppsättningen är tillräcklig, och vi måste vara medvetna om att minskningen kommer att gå på bekostnad av fler instruktioner per "betydande" operation.

Begreppet "ackumulator A"

Historisk konvention dedikerar ett register till ackumulatoren, ett "aritmetiskt organ" som bokstavligen ackumulerar sitt antal under en sekvens av aritmetiska operationer:

"Den första delen av vårt aritmetiska organ ... bör vara ett parallellt lagringsorgan som kan ta emot ett nummer och lägga till det i det som redan finns i det, vilket också kan rensa dess innehåll och som kan lagra vad det innehåller. Vi kommer att kalla ett sådant organ för en ackumulator . Det är ganska konventionellt i princip i tidigare och nuvarande datormaskiner av de mest varierade typerna, t.ex. skrivbordsmultiplikatorer, standard IBM -räknare, modernare relämaskiner, ENIAC "(fetstil i original: Goldstine och von Neumann , 1946; s. 98 i Bell och Newell 1971).

Ackumulatorn kommer emellertid på bekostnad av fler instruktioner per aritmetisk "operation", särskilt med avseende på vad som kallas "läs-modifiera-skriv" -instruktioner, såsom "Öka indirekt innehållet i registret som pekas på av register r2". "A" betecknar "ackumulator" -registret A:

Märka Instruktion A r2 377 426 kr Beskrivning
. . . 378 426 17
INCi (r2): CPY (i, r2, d, A) 17 378 426 17 Innehållet i r2 pekar på r378,426 med innehållet "17": kopiera detta till A
INC (A) 18 378 426 17 Innehåll i A
CPY (d, A, i, r2) 18 378 426 18 Innehållet i r2 pekar på r378,426: kopiera innehållet i A till r378,426

Om vi ​​håller oss till ett specifikt namn på ackumulatoren, t.ex. "A", kan vi antyda ackumulatoren i instruktionerna, till exempel

INC (A) = INCA

Men när vi skriver CPY -instruktionerna utan att ackumulatoren ropas ut är instruktionerna tvetydiga eller måste de ha tomma parametrar:

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

Historiskt vad som har hänt är att dessa två CPY -instruktioner har fått distinkta namn; det finns dock ingen konvention. Tradition (t.ex. Knuths (1973) imaginära MIX -dator) använder två namn som heter LOAD och STORE. Här lägger vi till parametern "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 )

Den typiska ackumulatorbaserade modellen kommer att ha alla sina två-variabla aritmetiska och konstanta operationer (t.ex. ADD (A, r), SUB (A, r)) användning (i) ackumulatorns innehåll, tillsammans med (ii) ett specificerat registerinnehåll . Envariabeloperationerna (t.ex. INC (A), DEC (A) och CLR (A)) kräver endast ackumulator. Båda instruktionstyperna sätter in resultatet (t.ex. summa, skillnad, produkt, kvot eller resterande) i ackumulatoren.

Exempel: INCA = [A] +1 → A
Exempel: ADDA (r s ) = [A] + [r s ] → A
Exempel: MULA (r s ) = [A] * [r s ] → A

Om vi ​​väljer det kan vi förkorta minnesvärdena eftersom minst ett källregister och destinationsregistret alltid är ackumulator A. Således har vi:

{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 ) , etc.)

Begreppet indirekt adressregister "N"

Om vår modell har en obegränsad ackumulator kan vi binda alla andra register? Inte förrän vi tillhandahåller minst ett obegränsat register från vilket vi härleder våra indirekta adresser.

Det minimalistiska tillvägagångssättet är att använda sig själv (Schönhage gör detta).

Ett annat tillvägagångssätt (Schönhage gör detta också) är att deklarera ett specifikt register som "indirekt adressregister" och begränsa indirektion i förhållande till detta register (Schonhages RAM0 -modell använder både A- och N -register för indirekta såväl som direkta instruktioner). Återigen har vårt nya register inget konventionellt namn - kanske "N" från "iNdex" eller "iNdirect" eller "adressnummer".

För maximal flexibilitet, som vi har gjort för ackumulator A-kommer vi att betrakta N som ännu ett register som kan ökas, minskas, rensas, testas, direktkopieras, etc. Återigen kan vi krympa instruktionen till en enda parameter som ger riktning och indirekt, till exempel.

LDAN (i/d) = CPY (i/d, N, d, A); LoaD -ackumulator via iNdirection -register
STAN (i/d) = CPY (d, A, i/d, N). Lagra ackumulator via iNdirection -register

Varför är detta ett så intressant tillvägagångssätt? Minst två skäl:

(1) En instruktionsuppsättning utan parametrar:

Schönhage gör detta för att producera sin RAM0 instruktionsuppsättning. Se avsnitt nedan.

(2) Minska ett RAM-minne till en maskin efter efterturnering:

Genom att utse oss som minimalister reducerar vi alla registren förutom ackumulator A och indirektionsregister N t.ex. r = {r0, r1, r2, ...} till en obegränsad sträng av (mycket-) begränsade kapacitetsduvhål. Dessa kommer inte att göra annat än att hålla (mycket) begränsade tal, t.ex. en ensam bit med värdet {0, 1}. På samma sätt krymper vi ackumulatorn till en enda bit. Vi begränsar all aritmetik till registren {A, N}, använder indirekta åtgärder för att dra in innehållet i registren i ackumulatoren och skriva 0 eller 1 från ackumulatoren till ett register:

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

Vi driver vidare och eliminerar A helt genom att använda två "konstanta" register som kallas "ERASE" och "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}

Byt namn på KOPIERINGSANVISNINGARNA och ring INC (N) = HÖGER, DEC (N) = VÄNSTER så har vi samma instruktioner som eftervridningsmaskinen, plus en extra CLRN:

{ERASE, PRINT, CLRN, HÖGER, VÄNSTER, JZ (i, N, I z ), JZ (I z ), H}

Turing ekvivalens för RAM med indirekt

I avsnittet ovan visade vi informellt att ett RAM -minne med en obegränsad indirektkapacitet ger en Post -Turing -maskin . Post -Turing -maskinen är Turing -ekvivalent, så vi har visat att RAM -minnet med indirektion är Turing -ekvivalent.

Vi ger här en lite mer formell demonstration. Börja med att designa vår modell med tre reserverade register "E", "P" och "N", plus en obegränsad uppsättning register 1, 2, ..., n till höger. Registren 1, 2, ..., n kommer att betraktas som "bandets rutor". Registrera "N" pekar på "den skannade rutan" som "huvudet" för närvarande observerar. "Huvudet" kan anses vara i villkorligt hopp-observera att det använder indirekt adressering (se Elgot-Robinson s. 398). När vi minskar eller ökar "N" kommer det (uppenbara) huvudet att "flytta vänster" eller "höger" längs rutorna. Vi kommer att flytta innehållet i "E" = 0 eller "P" = 1 till "skannade rutan" som N pekar på med hjälp av den indirekta CPY.

Det faktum att vår tejp är vänster gav oss ett mindre problem: När VÄNSTER inträffar måste våra instruktioner testas för att avgöra om innehållet i "N" är noll eller inte. i så fall bör vi låta räkningen vara "0" (detta är vårt val som designers - till exempel kan vi ha maskinen/modellen "utlös en händelse" efter eget val).

Instruktionsuppsättning 1 (utökad): {INC (N), DEC (N), CLR (N), CPY (d, r s , i, N), JZ (i, r, z), HALT}

Följande tabell definierar både Post-Turing-instruktionerna i termer av deras RAM-ekvivalenta instruktioner och ger ett exempel på hur de fungerar. Huvudets (uppenbara) placering längs bandet med registren r0-r5. . . visas skuggat:

Mnemonic märka: E P N r0 r1 r2 r3 r4 r5 etc. Åtgärd mot register Åtgärd på finite state machine Instruktionsregister IR
Start: 0 1 3 1 0
R höger: INC (N) 0 1 4 1 0 [N] +1 → N [IR] +1 → IR
P skriva ut: CPY (d, P, i, N) 0 1 4 1 1 [P] = 1 → [N] = r4 [IR] +1 → IR
E radera: CPY (d, E, i, N) 0 1 4 1 0 [E] = 0 → [N] = r4 [IR] +1 → IR
L vänster: JZ (i, N, slut) 0 1 4 1 0 ingen OM N = r4] = 0 DÅ "slut" → IR annars [IR] +1 → IR
DEC (N) 0 1 3 1 0 [N] -1 → N
J0 (stopp) jump_if_blank: JZ (i, N, slut) 0 1 3 1 0 ingen OM N = r3] = 0 DÅ "slut" → IR annars [IR] +1 → IR
J1 (stopp) jump_if_mark: JZ (i, N, stopp) 0 1 3 1 0 N = r3] → A OM N = r3] = 0 DÅ "slut" → IR annars [IR] +1 → IR
slutet . . . etc. 0 1 3 1 0
stanna: H 0 1 3 1 0 ingen [IR] +1 → IR

Exempel: Avgränsad indirektion ger en maskin som inte är Turing -ekvivalent

Under hela denna demonstration måste vi komma ihåg att instruktionerna i finite state -maskinens TABELL är begränsade , dvs ändliga :

"Förutom att det bara är en begränsad uppsättning regler som ger en sekvens av operationer för att lösa en specifik typ av problem, har en algoritm fem viktiga funktioner [slutlighet, bestämdhet, inmatning, utmatning, effektivitet]" (kursiv tillagd, Knuth s. 4 -7).
Svårigheten uppstår eftersom registren har uttryckliga "namn" (siffror) och vår maskin måste ringa ut alla med namn för att "komma åt" det.

Vi bygger den indirekta CPY (i, q, d, φ) med CASE -operatören. Målregistrets adress kommer att specificeras av innehållet i registret "q"; när CASE -operatören har fastställt vad detta nummer är kommer CPY direkt att deponera innehållet i registret med det numret i registret "φ". Vi behöver ett extra register som vi kommer att kalla "y"-det fungerar som en uppräknare.

Så följande är faktiskt en konstruktiv demonstration eller bevis på att vi verkligen kan simulera den indirekta CPY (i, q, d, φ) utan en "hårdvara" designändring till vår räknemaskin/modell. Observera emellertid att eftersom denna indirekta CPY är "begränsad" av storleken/omfattningen av den ändliga tillståndsmaskinen, kan en RASP som använder denna indirekta CPY bara beräkna de primitiva rekursiva funktionerna , inte hela sviten av mu -rekursiva funktioner .

CASE "operatören" beskrivs i Kleene (1952) (s. 229) och i Boolos-Burgess-Jeffrey (2002) (s. 74); de senare författarna betonar dess användbarhet. Följande definition är per Kleene men modifierad för att återspegla den välkända "IF-THEN-ELSE" -konstruktionen.

CASE -operatören "returnerar" ett naturligt tal till φ beroende på vilket "case" som är tillfredsställt, börjar med "case_0" och går successivt genom "case_last"; om inget fall är tillfredsställt returneras talet som kallas "standard" (aka "woops") till φ (här anger x några val av parametrar, t.ex. register q och strängen r0, ... rlast)):

Definition med fall φ ( x , y):

  • case_0: OM Q 0 ( x , y) är sant DÅ φ 0 ( x , y) ELSE
  • case_1: OM Q 1 ( x , y) är sant DÅ φ 1 ( x , y) ELSE
  • cases_2 till case_next_to_last: etc.. . . . . . . . ANNAN
  • case_last: IF Q last ( x , y) is true THEN φ last ( x , y) ELSE
  • standard: gör φ standard ( x , y)

Kleene kräver att "predikaten" Q n som gör testet alla utesluter varandra - "predikat" är funktioner som bara producerar {true, false} för utdata; Boolos-Burgess-Jeffrey lägger till kravet att ärendena är "uttömmande".

Vi börjar med ett nummer i registret q som representerar adressen till målregistret. Men vad är detta nummer? "Predikaten" kommer att testa det för att ta reda på det ena försöket efter det andra: JE (q, y, z) följt av INC (y). När numret har identifierats uttryckligen kopierar CASE -operatören direkt/uttryckligen innehållet i detta register till φ:

Definition av fall 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 DÅ CPY (r1, φ), J (exit) ELSE
  • case_2 genom case n: IF. . . DÅ. . . ANNAN
  • case_n: IF INC (y), [q] = [y] = n DÅ CPY (rn, φ), J (exit) ELSE
  • case_n+1 till case_last: IF. . . DÅ. . . ANNAN
  • case_last: IF INC (y), [q] = [y] = "last" THEN CPY (rlast, φ), J (exit) ELSE
  • standard: woops

Case_0 (bassteget i rekursionen på y) ser ut så här:

  • case_0 :
  • CLR (y); ställ in register y = 0
  • JE (q, y, _φ0 )
  • J ( case_1 )
  • _φ0: CPY (r0, φ)
  • J ( utgång )
  • case_1: etc.

Case_n (induktionssteget) ser ut så här; kom ihåg att varje instans av "n", "n+1", ..., "sista" måste vara ett klart naturligt tal:

  • case_n :
  • INC (y)
  • JE (q, y, _φn )
  • J ( case_n+1 )
  • _φn: CPY (rn, φ)
  • J ( utgång )
  • case__n+1: etc.

Case_last stoppar induktionen och avgränsar CASE -operatören (och begränsar därmed operatören "indirekt kopia"):

  • case_last :
  • INC (y)
  • JE (q, y, _φ senaste )
  • J ( woops )
  • _φlast : CPY (rlast, φ)
  • J ( utgång )
  • woops: hur hanterar vi ett försök utanför gränserna?
  • utgång: etc.

Om CASE kunde fortsätta i det oändliga skulle det vara mu -operatören . Men det kan den inte - dess slutliga tillståndsmaskins "tillståndsregister" har nått sitt maximala antal (t.ex. 65365 = 11111111,11111111 2 ) eller dess tabell har slut på instruktioner; det är trots allt en ändlig maskin.

Exempel på modeller

Registrera-för-registrera-modellen ("läs-ändra-skriva") av Cook and Reckhow (1973)

Den vanligt förekommande Cook- och Rechkow-modellen är lite som den ternära registret Malzek-modellen (skriven med Knuth mnemonics-de ursprungliga instruktionerna hade ingen mnemonik utom TRA, Read, Print).

  • LOAD ( C, rd ) ; C → rd, C är vilket heltal som helst
Exempel: LOAD ( 0, 5 )rensar register 5.
  • ADD ( rs1, rs2, rd ) ; [rs1] + [rs2] → rd, registren kan vara desamma eller olika;
Exempel: ADD ( A, A, A )fördubblar innehållet i register A.
  • SUB ( rs1, rs2, rd ) ; [rs1] - [rs2] → rdkan registren vara desamma eller olika:
Exempel: SUB ( 3, 3, 3 )rensar register 3.
  • COPY ( i, rp, d, rd ) ; [[rp] ] → rd, Kopiera indirekt innehållet i källregistret som pekarregistret r p pekar in i destinationsregistret.
  • COPY ( d, rs, i, rp ) ; [rs] → [rp]. Kopiera innehållet i källregistret r s till destinationsregistret som pekarregistret p s pekar på .
  • JNZ ( r, Iz ) ;Villkorligt hopp om [r] är positivt; dvs OM [r]> 0 Därefter hoppa till instruktion z annars fortsätt i sekvens (Cook and Reckhow kallar detta: "TRAnsfer control to line m if Xj> 0")
  • READ ( rd ) ;kopiera "ingången" till destinationsregistret r d
  • PRINT ( rs ) ;kopiera innehållet i källregistret r s till "utgången".

Schönhages RAM0 och RAM1 (1980)

Schönhage (1980) beskriver en mycket primitiv, atomiserad modell vald för sitt bevis på likvärdigheten i hans SMM -pekarmaskinmodell :

"För att undvika någon tydlig adressering har RAM0 ackumulatorn med innehåll z och ett ytterligare adressregister med aktuellt innehåll n (initialt 0)" (s. 494)

RAM1-modell : Schönhage visar hur hans konstruktion kan användas för att bilda den mer vanliga, användbara formen av "efterträdare" -liknande RAM (med hjälp av denna artikels mnemonik):

  • LDA k ; k --> A , k är en konstant, ett uttryckligt tal som "47"
  • LDA ( d, r ) ; [r] → A ; ladda direkt A
  • LDA ( i, r ) ; [[r]] → A ; indirekt last A
  • STA ( d, r ) ; [A] → r ; lagra A direkt
  • STA ( i, r ) ; [A] → [r] ; indirekt lagra A
  • JEA ( r, z ) ; IF [A] = [r] then Iz else continue
  • INCA ; [A] + 1 --> A

RAM0 -modell : Schönhages RAM0 -maskin har 6 instruktioner indikerade med en enda bokstav (den sjätte "C xxx" verkar innebära att "hoppa över nästa parameter". Schönhage betecknade ackumulatoren med "z", "N" med "n", etc. I stället för Schönhages mnemonik kommer vi att använda mnemoniken som utvecklats ovan.

  • (Z), CLRA: 0 → A
  • (A), INCA: [A] +1 → A
  • (N), CPYAN: [A] → N
  • (A), LDAA: [[A]] → A ; innehållet i A -punkter för att registrera adress; sätt registerinnehållet i A
  • (S), STAN: [A] → [N] ; innehållet i N -punkter för att registrera adress; sätta innehållet i A i register som N pekar på
  • (C), JAZ ( z ): [A] = 0 then go to Iz ; tvetydig i sin behandling

Indirektion kommer (i) från CPYAN (kopiera/överföra innehåll A till N) som arbetar med store_A_via_N STAN och från (ii) den säregna indirektinstruktionen LDAA ( [[A]] → [A] ).

Fotnoter

Ändlig vs obegränsad

Definitionsfaktumet att alla typer av räknemaskiner utan ett obegränsat register- "adress" -register måste specificera ett register "r" efter namn indikerar att modellen kräver att "r" är ändligt , även om det är "obegränsat" i den meningen att modell innebär ingen övre gräns för antalet register som är nödvändiga för att utföra sitt / sina jobb. Till exempel kräver vi inte r <83,617,563,821,029,283,746 eller r <2^1 000,001, etc.

Således kan vår modell "expandera" antalet register, om det behövs för att utföra en viss beräkning. Men detta gör medelvärdet att oavsett antalet modellen expanderar måste vara ändlig  - det måste vara vänd med ett naturligt tal: ω är inte ett alternativ .

Vi kan undvika denna begränsning genom att tillhandahålla ett obegränsat register för att tillhandahålla adressen till registret som anger en indirekt adress.

Se även

externa länkar

Referenser

Med några få undantag är dessa referenser desamma som hos Register machine .

    • Goldstine, Herman H. och von Neumann, John, "Planering och kodning av problemen för ett elektroniskt datorinstrument", Rep. 1947, Institute for Advanced Study , Princeton. Omtryckt på s. 92–119 i Bell, C. Gordon och Newell, Allen (1971), Computer Structures: Readings and Exempel , 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. Den ursprungliga Boolos-Jeffrey-texten har omfattande reviderats av Burgess: mer avancerad än en inledande lärobok. "Abacus -maskin" -modellen är omfattande utvecklad i kapitel 5 Abacus Computability ; det är en av tre modeller som behandlas och jämförs omfattande-Turing-maskinen (fortfarande i Boolos ursprungliga 4-tupelform) och rekursion av de andra två.
  • Arthur Burks , Herman Goldstine , John von Neumann (1946), Preliminär diskussion om den logiska designen av ett elektroniskt beräkningsinstrument , återtryckt s. 92ff i Gordon Bell och Allen Newell (1971), Computer Structures: Readings and Exempel , mcGraw-Hill Book Company, New York. ISBN  0-07-004357-4 .
  • Stephen A. Cook och 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 och Abraham Robinson (1964), Random-Access Stored-Program Machines, an Approach to Programming Language , Journal of the Association for Computing Machinery, Vol. 11, nr 4 (oktober 1964), s. 365–399.
  • J. Hartmanis (1971), "Computational Complexity of Random Access Stored Program Machines", Mathematical Systems Theory 5, 3 (1971) s. 232–245.
  • John Hopcroft , Jeffrey Ullman (1979). Introduction to Automata Theory, Languages ​​and Computation , 1st ed., Reading Mass: Addison-Wesley. ISBN  0-201-02988-X . En svår bok centrerad kring frågorna om maskintolkning av "språk", NP-fullständighet etc.
  • Stephen Kleene (1952), Introduction to Metamathematics , North-Holland Publishing Company, Amsterdam, Nederländerna. ISBN  0-7204-2103-9 .
  • Donald Knuth (1968), The Art of Computer Programming , andra upplagan 1973, Addison-Wesley, Reading, Massachusetts. Jfr sid 462-463 där han definierar "en ny typ av abstrakt maskin eller" automat "som behandlar länkade strukturer."
  • Joachim Lambek (1961, mottagen 15 juni 1961), How to Program an Infinite Abacus , Mathematical Bulletin, vol. 4, nej. 3. September 1961 sidorna 295-302. I sitt tillägg II föreslår Lambek en "formell definition av" program ". Han hänvisar till Melzak (1961) och Kleene (1952) Introduction to Metamathematics .
  • ZA Melzak (1961, mottagen 15 maj 1961), An informal Arithmetical Approach to Computability and Computation , Canadian Mathematical Bulletin , vol. 4, nej. 3. September 1961 sidorna 279-293. Melzak erbjuder inga referenser, men erkänner "fördelen med samtal med Dr R. R. Hamming, D. McIlroy och V. Vyssots från Bell Phone Laborators och med Dr. H. Wang från Oxford University."
  • Marvin Minsky (1961). "Rekursiv olöslighet för Posts problem med" Tag "och andra ämnen i teori om dragmaskiner". Annals of Mathematics . The Annals of Mathematics, vol. 74, nr 3. 74 (3): 437–455. doi : 10.2307/1970290 . JSTOR  1970290 .
  • Marvin Minsky (1967). Beräkning: Finite and Infinite Machines (1: a upplagan). Englewood Cliffs, NJ: Prentice-Hall, Inc.Se särskilt kapitel 11: Modeller som liknar digitala datorer och kapitel 14: Mycket enkla baser för beräkning . I det tidigare kapitlet definierar han "Programmaskiner" och i det senare kapitlet diskuterar han "Universella programmaskiner med två register" och "... med ett register", etc.
  • John C. Shepherdson och HE Sturgis (1961) erhöll december 1961 Computability of Recursive Functions , Journal of the Association of Computing Machinery (JACM) 10: 217-255, 1963. Ett extremt värdefullt referenspapper. I sin bilaga A citerar författarna 4 andra med hänvisning till "Minimalitet av instruktioner som används i 4.1: Jämförelse med liknande system".
  • Kaphengst, Heinz, Eine Abstrakte programmgesteuerte Rechenmaschine ' , Zeitschrift fur mathematische Logik und Grundlagen der Mathematik: 5 (1959), 366-379.
  • Ershov, AP Om operatörsalgoritmer , (ryska) Dok. Akad. Nauk 122 (1958), 967-970. Engelsk översättning, Automat. Express 1 (1959), 20-23.
  • Péter, Rózsa Graphschemata und rekursive 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. Vol. 9, nr 3, augusti 1980. I vilken Schōnhage visar likvärdigheten för hans SMM med "efterföljaren RAM" (Random Access Machine), etc. resp. Storage Modification Machines , in Theoretical Computer Science (1979), s. 36–37
  • Peter van Emde Boas , "Maskinmodeller och simuleringar" s. 3–66, i: Jan van Leeuwen , red. Handbok i teoretisk datavetenskap. Volym A: Algoritmer och komplexitet , The MIT PRESS/Elsevier, 1990. ISBN  0-444-88071-2 (volym A). QA 76.H279 1990. van Emde Boas behandling av SMM framgår av sidorna 32–35. Denna behandling förtydligar Schōnhage 1980 - den följer noga men expanderar något Schōnhage -behandlingen något. Båda referenserna kan behövas för effektiv förståelse.
  • Hao Wang (1957), En variant på Turings teori om datormaskiner , JACM (Journal of the Association for Computing Machinery) 4; 63-92. Presenterades vid sammanträdet i föreningen, 23–25 juni 1954.