Registrera maskinen

Inom matematisk logik och teoretisk datavetenskap är en registermaskin en generisk klass av abstrakta maskiner som används på ett sätt som liknar en Turing-maskin . Alla modeller är Turing likvärdiga .

Översikt

Registermaskinen får sitt namn från dess användning av ett eller flera " register ". Till skillnad från bandet och huvudet som används av en Turing-maskin använder modellen flera unikt adresserade register, som vart och ett har ett enda positivt heltal .

Det finns minst fyra underklasser i litteraturen, här listade från de mest primitiva till de mest som en dator :

Räknarmaskin – den mest primitiva och reducerade teoretiska modellen av en datorhårdvara. Saknar indirekt adressering. Instruktioner finns i finita tillståndsmaskinen på samma sätt som Harvard-arkitekturen .
Pekarmaskin – en blandning av räknarmaskin och RAM-modeller. Mindre vanligt och mer abstrakt än båda modellerna. Instruktioner finns i den finita tillståndsmaskinen på samma sätt som Harvard-arkitekturen.
Random-Access Machine (RAM) – en räknarmaskin med indirekt adressering och vanligtvis en utökad instruktionsuppsättning. Instruktioner finns i den finita tillståndsmaskinen på samma sätt som Harvard-arkitekturen.
Random access stored-program machine model (RASP) – ett RAM med instruktioner i sina register analogt med Universal Turing-maskinen ; sålunda är det ett exempel på von Neumann-arkitekturen . Men till skillnad från en dator är modellen idealiserad med i praktiken oändliga register (och om de används, i praktiken oändliga specialregister som en ackumulator). Jämfört med en dator är instruktionsuppsättningen mycket reducerad i antal och komplexitet.

Varje korrekt definierad registermaskinmodell är Turing-ekvivalent . Beräkningshastigheten är mycket beroende av modellens specifikation.

Inom praktisk datavetenskap används ibland ett liknande koncept som kallas en virtuell maskin för att minimera beroenden av underliggande maskinarkitekturer. Sådana maskiner används också för undervisning. Termen "registermaskin" används ibland för att referera till en virtuell maskin i läroböcker.

Formell definition

En registermaskin består av:

Ett obegränsat antal märkta, diskreta, ogränsade register obegränsade i omfattning (kapacitet) : en ändlig (eller oändlig i vissa modeller) uppsättning register $r_{0}\ldots r_{n}$ vart och ett anses vara vara av oändlig utsträckning och var och en har ett enda icke-negativt heltal (0, 1, 2, ...). Registren kan göra sin egen aritmetik, eller så kan det finnas ett eller flera specialregister som gör aritmetiken, t.ex. ett "ackumulator" och/eller "adressregister". Se även Slumpmässig åtkomstmaskin .
Räknare eller märken : diskreta, oskiljaktiga föremål eller märken av endast en sort som passar modellen. I den mest reducerade räknemaskinsmodellen , per varje aritmetisk operation läggs endast ett objekt/märke till eller tas bort från dess plats/tejp. I vissa modeller av räknare (t.ex. Melzak (1961), Minsky (1961)) och de flesta RAM- och RASP-modeller kan mer än ett objekt/märke läggas till eller tas bort i en operation med "addition" och vanligtvis "subtraktion"; ibland med "multiplikation" och/eller "division". Vissa modeller har kontrolloperationer som "kopiera" (variant: "flytta", "ladda", "lagra") som flyttar "klumpar" av objekt/märken från register till register i en åtgärd.
En (mycket) begränsad uppsättning instruktioner : instruktionerna tenderar att delas upp i två klasser: aritmetik och kontroll. Instruktionerna är hämtade från de två klasserna för att bilda "instruktionsuppsättningar", så att en instruktionsuppsättning måste tillåta att modellen är Turingekvivalent (den måste kunna beräkna vilken partiell rekursiv funktion som helst ).
1. Aritmetik : aritmetiska instruktioner kan fungera på alla register eller på bara ett speciellt register (t.ex. ackumulator). De vanligtvis från följande uppsättningar (men undantag finns i överflöd):
  - Räknarmaskin: { Öka (r), Minska (r), Rensa till noll (r) }
  - Reducerat RAM, RASP: { Öka (r), Minska (r), Rensa-till-noll (r), Ladda-omedelbar-konstant k, Addera (r 1 ,r ₂ ) _, korrekt-Subtrahera (r ₁ , r ₂ ), Inkrementera ackumulator, Minska ackumulator, Rensa ackumulator, Lägg till ackumulatorinnehåll i register r, korrekt-Subtrahera från ackumulatorinnehåll i register r, }
  - Förstärkt RAM, RASP: Alla reducerade instruktioner plus: { Multiplicera, dividera, olika booleska bitvis (vänsterskift, bittest, etc.)}
2. Kontroll :
  - Räknarmaskiner: valfritt { Copy (r ₁ ,r ₂ ) }
  - RAM- och RASP-modeller: de flesta har { Copy (r ₁ ,r ₂ ) }, eller { Ladda ackumulator från r, Lagra ackumulator i r, Ladda ackumulator med omedelbar konstant }
  - Alla modeller: minst ett villkorligt "hopp" (gren, goto) efter test av ett register t.ex. { Hoppa-om-noll, Hoppa-om-inte-noll (dvs. Hoppa-om-positivt), Hoppa-om-lika, Hoppa-om-inte lika }
  - Alla modeller valfria: { ovillkorligt programhopp (goto) }
3. Registeradresseringsmetod :
  - Räknarmaskin: ingen indirekt adressering, omedelbara operander möjliga i högt atomiserade modeller
  - RAM och RASP: indirekt adressering tillgänglig, omedelbara operander typiska
4. Ingång-utgång : tillval i alla modeller
Statsregister : Ett speciellt instruktionsregister "IR", ändligt och separat från registren ovan, lagrar den aktuella instruktionen som ska utföras och dess adress i TABELLEN med instruktioner; detta register och dess TABELL finns i den finita tillståndsmaskinen.
- IR är förbjudet för alla modeller. När det gäller RAM och RASP, i syfte att bestämma "adressen" till ett register, kan modellen välja antingen (i) i fallet med direkt adressering—den adress som anges i TABELL och tillfälligt placerad i IR eller ( ii) vid indirekt adressering—innehållet i registret som anges av IR:s instruktion.
- IR är inte "programräknaren" (PC) för RASP (eller konventionell dator). PC:n är bara ett annat register som liknar en ackumulator, men dedikerat till att hålla numret på RASP:s aktuella registerbaserade instruktion. Således har en RASP två "instruktions/program"-register - (i) IR (finita tillståndsmaskinens instruktionsregister) och (ii) en PC (programräknare) för programmet som finns i registren. (Som ett register dedikerat till "datorn", kan en RASP dedikera ett annat register till "Program-instruktionsregistret" (med valfritt antal namn som "PIR, "IR", "PR", etc.)
Lista över märkta instruktioner, vanligtvis i sekventiell ordning : En ändlig lista med instruktioner $I_{1}\ldots I_{m}$ $I_{1}\ldots I_{m}$ . I fallet med räknarmaskinen, direktåtkomstmaskinen (RAM) och pekarmaskinen finns instruktionsminnet i "TABELLEN" i den finita tillståndsmaskinen; sålunda är dessa modeller exempel på Harvard-arkitekturen. I fallet med RASP finns programminnet i registren; sålunda är detta ett exempel på von Neumann-arkitekturen. Se även Maskin med slumpmässig tillgång och slumpmässig åtkomst med lagrat program. Vanligtvis, precis som datorprogram , listas instruktionerna i sekventiell ordning; om inte ett hopp lyckas fortsätter standardsekvensen i numerisk ordning. Ett undantag från detta är abacus (Lambek (1961), Minsky (1961)) räknarmaskinmodeller – varje instruktion har minst en "nästa" instruktionsidentifierare "z", och den villkorliga grenen har två.
- Observera också att kulramsmodellen kombinerar två instruktioner, JZ sedan DEC: t.ex. { INC ( r, z ), JZDEC ( r, z _true , z _false ) }. Se McCarthy Formalism för mer om det villkorliga uttrycket "IF r=0 THEN z _true ELSE z _false " (jfr McCarthy (1960)).

Historisk utveckling av registermaskinmodellen

Två trender dök upp i början av 1950-talet – den första som karakteriserade datorn som en Turingmaskin, den andra för att definiera datorliknande modeller – modeller med sekventiella instruktionssekvenser och villkorade hopp – med kraften hos en Turingmaskin, dvs en s.k. Turing-ekvivalens. Behovet av detta arbete utfördes i samband med två "hårda" problem: det olösliga ordproblemet som Emil Post ställer — hans problem med "tagg" — och det mycket "hårda" problemet med Hilberts problem — den tionde frågan kring diofantiska ekvationer . Forskare letade efter Turing-ekvivalenta modeller som var mindre "logiska" till sin natur och mer "aritmetiska" (jfr Melzak (1961) s. 281, Shepherdson–Sturgis (1963) s. 218).

Den första trenden – mot att karakterisera datorer – tycks ha sitt ursprung hos Hans Hermes (1954), Rózsa Péter (1958) och Heinz Kaphengst (1959), den andra trenden med Hao Wang (1954, 1957) och, som nämnts ovan, främjade tillsammans med Zdzislaw Alexander Melzak (1961), Joachim Lambek (1961) och Marvin Minsky (1961, 1967).

De fem sista namnen listas uttryckligen i den ordningen av Yuri Matiyasevich . Han följer upp med:

"Registermaskiner [vissa författare använder "registermaskin" synonymt med "motmaskin"] är särskilt lämpliga för att konstruera diofantiska ekvationer. Liksom Turing-maskiner har de mycket primitiva instruktioner och dessutom handlar de om siffror" (Yuri Matiyasevich ( 1993), Hilberts tionde problem , kommentar till kapitel 5 i boken, på http://logic.pdmi.ras.ru/yumat/H10Pbook/commch_5htm .)

Det verkar som om Lambek, Melzak, Minsky och Shepherdson och Sturgis oberoende av varandra förutsåg samma idé samtidigt. Se anmärkning om prioritet nedan.

Historien börjar med Wangs modell.

Wangs (1954, 1957) modell: Post–Turing-maskin

Wangs arbete följde från Emil Posts (1936) papper och ledde Wang till sin definition av sin Wang B-maskin - en tvåsymbols Post-Turing-maskinberäkningsmodell med endast fyra atominstruktioner:

{ VÄNSTER, HÖGER, PRINT, JUMP_if_marked_to_instruction_z }

Till dessa fyra lade både Wang (1954, 1957) och sedan CY Lee (1961) till ytterligare en instruktion från postuppsättningen { ERASE }, och sedan ett inläggs ovillkorliga hopp { JUMP_to_ instruction_z } (eller för att göra saker enklare, det villkorliga hoppet JUMP_IF_blank_to_instruction_z, eller båda. Lee döpte detta till en "W-machine"-modell:

{ VÄNSTER, HÖGER, PRINT, ERASE, JUMP_if_marked, [kanske JUMP eller JUMP_IF_blank] }

Wang uttryckte hopp om att hans modell skulle vara "ett närmande" (s. 63) mellan teorin om Turing-maskiner och datorns praktiska värld.

Wangs arbete var mycket inflytelserik. Vi finner honom refererad av Minsky (1961) och (1967), Melzak (1961), Shepherdson och Sturgis (1963). Shepherdson och Sturgis (1963) påpekar faktiskt att:

"...vi har försökt att ta ett steg längre "närmandet" mellan de praktiska och teoretiska aspekterna av beräkning som föreslagits av Wang" (s. 218)

Martin Davis utvecklade så småningom denna modell till Post-Turing-maskinen (2-symboler).

Svårigheter med Wang/Post-Turing-modellen :

Förutom att det fanns ett problem: Wang-modellen (de sex instruktionerna för 7-instruktions Post-Turing-maskinen) var fortfarande en Turing-liknande enhet med en band, hur trevligt dess sekventiella programinstruktionsflöde än kan vara . Både Melzak (1961) och Shepherdson och Sturgis (1963) observerade detta (i samband med vissa bevis och undersökningar):

"...en Turing-maskin har en viss opacitet... en Turing-maskin är långsam i (hypotetisk) drift och vanligtvis komplicerad. Detta gör det ganska svårt att designa den, och ännu svårare att undersöka sådana frågor som tid eller lagring optimering eller en jämförelse mellan effektiviteten hos två algoritmer. (Melzak (1961) s. 281)

"... även om det inte är svårt ... bevis är komplicerade och tråkiga att följa av två skäl: (1) En Turing-maskin har bara huvudet så att man är skyldig att dela upp beräkningen i mycket små steg av operationer på en enda siffra. (2) Den har bara ett band så att man måste anstränga sig för att hitta numret man vill arbeta på och hålla det åtskilt från andra nummer” (Shepherdson och Sturgis (1963) s. 218).

Som exempel på Turing-maskinexempel , Post–Turing-maskin och partiell funktion visar, kan arbetet vara "komplicerat".

Minsky, Melzak-Lambek och Shepherdson–Sturgis modeller "klippte tejpen" i många

Så varför inte "klippa av bandet" så att var och en är oändligt lång (för att få plats med heltal i alla storlekar) men vänsterändad, och kalla dessa tre band "Post–Turing (dvs. Wang-liknande) band"? De enskilda huvudena flyttas åt vänster (för minskning) och höger (för ökning). I en mening indikerar huvuden "topparna på stapeln" av sammanlänkade märken. Eller i Minsky (1961) och Hopcroft och Ullman (1979, s. 171ff) är tejpen alltid tom förutom ett märke i den vänstra änden - vid något tillfälle skrivs eller raderas ett huvud aldrig.

Vi måste bara vara noga med att skriva våra instruktioner så att ett test-för-noll och hopp inträffar innan vi minskar, annars kommer vår maskin att "falla av slutet" eller "stöta mot slutet" - vi kommer att ha en instans av en partiell funktion . Innan en minskning måste vår maskin alltid ställa frågan: "Är tejpen/disken tom? I så fall kan jag inte sänka, annars kan jag."

Minsky (1961) och Shepherdson–Sturgis (1963) bevisar att endast ett fåtal band – så få som ett – fortfarande tillåter maskinen att vara Turing-ekvivalent OM data på bandet representeras som ett Gödel-nummer ( eller något annat unikt kodningsbart- avkodningsbart nummer); detta nummer kommer att utvecklas allteftersom beräkningen fortskrider. I versionen med ett band med Gödel-nummerkodning måste räknaren kunna (i) multiplicera Gödel-talet med en konstant (siffrorna "2" eller "3"), och (ii) dividera med en konstant (siffrorna "2" eller "3") och hoppa om resten är noll. Minsky (1967) visar att behovet av denna bisarra instruktionsuppsättning kan minskas till { INC (r), JZDEC (r, z) } och bekvämlighetsinstruktionerna { CLR (r), J (r) } om två band är tillgängliga . En enkel Gödelisering krävs dock fortfarande. Ett liknande resultat visas i Elgot–Robinson (1964) med avseende på deras RASP-modell.

Melzaks (1961) modell är annorlunda: klumpar av småsten går in i och ut ur hål

Melzaks (1961) modell är väsentligt annorlunda. Han tog sin egen modell, vände banden vertikalt, kallade dem "hål i marken" för att fyllas med "stensräknare". Till skillnad från Minskys "ökning" och "minskning" tillät Melzak korrekt subtraktion av varje antal småsten och "lägg till" av alla antal småsten.

Han definierar indirekt adressering för sin modell (s. 288) och ger två exempel på dess användning (s. 89); hans "bevis" (sid. 290-292) på att hans modell är Turing-ekvivalent är så skissartad att läsaren inte kan avgöra om han avsett att den indirekta adressen skulle vara ett krav för beviset.

Arvet efter Melzaks modell är Lambeks förenkling och återuppkomsten av hans mnemoniska konventioner i Cook and Reckhow 1973.

Lambek (1961) finfördelar Melzaks modell till Minsky-modellen (1961): INC och DEC-med-test

Lambek (1961) tog Melzaks ternära modell och finfördelade den till de två unära instruktionerna – X+, X- om möjligt annat hopp – exakt samma två som Minsky (1961) hade kommit på.

Liksom Minsky (1961)-modellen utför dock Lambek-modellen sina instruktioner på ett standardsekventiellt sätt - både X+ och X- bär identifieraren för nästa instruktion, och X- bär också hopp-till-instruktionen om nollan -testet är framgångsrikt.

Elgot–Robinson (1964) och problemet med RASP utan indirekt adressering

En RASP eller slumpmässigt åtkomst lagrad programmaskin börjar som en räknarmaskin med dess "instruktionsprogram" placerat i dess "register". Analogt med, men oberoende av, den finita tillståndsmaskinens "Instruktionsregister", upprätthåller åtminstone ett av registren (med smeknamnet "programräknaren" (PC)) och ett eller flera "tillfälliga" register ett register över och fungerar på, den aktuella instruktionens nummer. Den finita tillståndsmaskinens TABELL av instruktioner är ansvarig för (i) att hämta den aktuella programinstruktionen från det korrekta registret, (ii) tolka programinstruktionen , ( iii) hämta operander specificerade av programinstruktionen , och (iv) exekvera programinstruktionen .

Förutom att det finns ett problem: Om baserad på diskmaskinens chassi är denna datorliknande, kommer von Neumann -maskinen inte att vara Turing-ekvivalent. Den kan inte beräkna allt som är beräkningsbart. I sig är modellen begränsad av storleken på dess (mycket-) finita tillståndsmaskins instruktioner. Den räknarmaskinbaserade RASP kan beräkna vilken primitiv rekursiv funktion som helst (t.ex. multiplikation) men inte alla mu-rekursiva funktioner (t.ex. Ackermann-funktionen ).

Elgot–Robinson undersöker möjligheten att tillåta deras RASP-modell att "själv modifiera" sina programinstruktioner. Idén var en gammal, föreslog av Burks-Goldstine-von Neumann (1946-7), och ibland kallad "den beräknade goto". Melzak (1961) nämner specifikt "beräknad goto" vid namn men förser istället sin modell med indirekt adressering.

Beräknad goto: Ett RASP -program med instruktioner som modifierar "goto-adressen" i en programinstruktion för villkorligt eller ovillkorligt hopp .

Men detta löser inte problemet (om man inte tar till Gödel-siffror ). Vad som är nödvändigt är en metod för att hämta adressen till en programinstruktion som ligger (långt) "bortom/över" den övre gränsen för den finita tillståndsmaskinens instruktionsregister och TABELL.

Exempel: En räknarmaskin utrustad med endast fyra obundna register kan t.ex. multiplicera två valfria tal ( m, n ) tillsammans för att ge p—och därmed vara en primitiv rekursiv funktion—oavsett hur stora talen m och n är; dessutom krävs mindre än 20 instruktioner för att göra detta! t.ex. { 1: CLR ( p ), 2: JZ ( m, klar ), 3 yttre_slinga: JZ ( n, klar ), 4: CPY ( m, temp ), 5: inner_loop: JZ ( m, yttre_slinga ), 6: DEC ( m ), 7: INC ( p ), 8: J ( inner_loop ), 9: yttre_loop: DEC ( n ), 10 J ( yttre_loop ), HALT } Men med endast 4 register har denna maskin inte i närheten av tillräckligt

stor att bygga en RASP som kan köra multiplikationsalgoritmen som ett program . Oavsett hur stor vi bygger vår finita tillståndsmaskin kommer det alltid att finnas ett program (inklusive dess parametrar) som är större. Så per definition kan den avgränsade programmaskinen som inte använder obegränsade kodningstrick som Gödel-tal inte vara universell .

Minsky (1967) antyder frågan i sin undersökning av en räknarmaskin (han kallar dem "programdatormodeller") utrustad med instruktionerna { CLR (r), INC (r) och RPT ("a" gånger instruktionerna m till n) }. Han berättar inte hur vi ska lösa problemet, men han observerar att:

"... programdatorn måste ha något sätt att hålla reda på hur många RPT som återstår att göra, och detta kan förbruka en viss mängd lagringsutrymme som tillåts i den ändliga delen av datorn. RPT-operationer kräver oändliga egna register , i allmänhet, och de måste behandlas annorlunda än de andra typerna av operationer vi har övervägt." (sid. 214)

₀₀₀₀ Men Elgot och Robinson löser problemet: de utökar sin P RASP med en indexerad uppsättning instruktioner – en något mer komplicerad (men mer flexibel) form av indirekt adressering. Deras P'- modell adresserar registren genom att lägga till innehållet i "bas"-registret (specificerat i instruktionen) till "index" som uttryckligen anges i instruktionen (eller vice versa, byta ut "bas" och "index"). Således har de indexerande P'- instruktionerna en parameter mer än de icke-indexerande P- instruktionerna:

Exempel: INC ( r _bas , index ); effektiv adress kommer att vara [r _bas ] + index, där det naturliga talet "index" härleds från själva maskininstruktionen i finita tillstånd.

Hartmanis (1971)

1971 har Hartmanis förenklat indexeringen till indirekt för användning i sin RASP-modell.

Indirekt adressering: Ett pekarregister förser den finita tillståndsmaskinen med adressen till målregistret som krävs för instruktionen. Sagt på ett annat sätt: Innehållet i pekarregistret är adressen till "målregistret" som ska användas av instruktionen. Om pekarregistret är obegränsat kommer RAM-minnet och en lämplig RASP byggd på dess chassi att vara Turing-ekvivalent. Målregistret kan fungera antingen som ett käll- eller destinationsregister, såsom specificeras av instruktionen.

Observera att den finita tillståndsmaskinen inte behöver explicit specificera detta målregisters adress. Den säger bara till resten av maskinen: Hämta innehållet i registret som mitt pekarregister pekar på och gör sedan xyz med det. Det måste uttryckligen ange detta pekarregister (t.ex. "N", eller "72" eller "PC", etc.) med namn, men det behöver inte veta vilket nummer pekarregistret faktiskt innehåller ( kanske 279 431).

Cook och Reckhow (1973) beskriver RAM-minnet

Cook och Reckhow (1973) citerar Hartmanis (1971) och förenklar hans modell till vad de kallar en slumpmässigt åtkomstmaskin (RAM – dvs en maskin med indirektion och Harvard-arkitekturen). På sätt och vis är vi tillbaka till Melzak (1961) men med en mycket enklare modell än Melzaks.

Företräde

Minsky arbetade vid MIT Lincoln Laboratory och publicerade sitt arbete där; hans papper mottogs för publicering i Annals of Mathematics den 15 augusti 1960, men publicerades inte förrän i november 1961. Medan mottagandet inträffade ett helt år innan Melzaks och Lambeks arbete mottogs och publicerades (mottogs, respektive, maj och 15 juni , 1961, och publicerad sida vid sida september 1961). Att (i) båda var kanadensare och publicerade i Canadian Mathematical Bulletin , (ii) ingendera skulle ha haft hänvisning till Minskys arbete eftersom det ännu inte publicerats i en referentgranskad tidskrift, men (iii) Melzak refererar till Wang och Lambek referenser Melzak, får en att anta att deras arbete skedde samtidigt och oberoende.

Nästan exakt samma sak hände med Shepherdson och Sturgis. Deras papper mottogs i december 1961 - bara några månader efter att Melzak och Lambeks arbete mottagits. Återigen hade de liten (högst 1 månad) eller ingen fördel av att granska Minskys arbete. De var noga med att observera i fotnoter att tidningar av Ershov, Kaphengst och Peter hade "nyligen dykt upp" (s. 219). Dessa publicerades mycket tidigare men förekom på tyska i tyska tidskrifter så att frågor om tillgänglighet presenterar sig själva.

Den slutliga artikeln av Shepherdson och Sturgis publicerades inte i en peer-reviewed tidskrift förrän 1963. Och som de rättvist och ärligt noterar i sin Appendix A, "systemen" av Kaphengst (1959), Ershov (1958), Peter (1958) är alla så lika de resultat som erhölls senare att de inte går att särskilja från en uppsättning av följande:

producera 0 dvs 0 → n

inkrementera ett tal dvs n+1 → n

"dvs att utföra operationerna som genererar de naturliga talen" (s. 246)

kopiera ett tal dvs n → m

för att "ändra förloppet av en beräkning", antingen jämföra två tal eller minska till 0

Faktum är att Shepherson och Sturgis avslutar

"De olika minimalsystemen är väldigt lika"(s. 246)

Efter publiceringsdatum var arbetet av Kaphengst (1959), Ershov (1958), Peter (1958) först.

Se även

Räknarmaskin
- Räknarmaskin modell
Pekarmaskin
Slumpmässig åtkomstmaskin
Maskin med slumpmässig åtkomst med lagrat program
Turing maskin
Wang B-maskin
Post-Turingmaskin - beskrivning plus exempel
Algoritm
- Algoritmkarakteriseringar
Stoppa problem
Upptagen bäver
Stackmaskin
WDR pappersdator

Bibliografi

Bakgrundstexter: Följande litteraturförteckning över källdokument innehåller ett antal texter som ska användas som bakgrund. Matematiken som ledde till mängden tidningar om abstrakta maskiner på 1950- och 1960-talen finns i van Heijenoort (1967) – en samling originalpapper som sträcker sig över 50 år från Frege (1879) till Gödel (1931). Davis (red.) The Undecidable (1965) bär facklan vidare med början med Gödel (1931) genom Gödels (1964) postscriptum (s. 71); originalhandlingarna av Alan Turing (1936-7) och Emil Post (1936) ingår i The Undecidable . Mathematics of Church, Rosser and Kleene som visas som omtryck av originalpapper i The Undecidable förs vidare i Kleene (1952), en obligatorisk text för alla som strävar efter en djupare förståelse av matematiken bakom maskinerna. Både Kleene (1952) och Davis (1958) refereras av ett antal tidningar.

För en bra behandling av räknaren, se Minsky (1967) Kapitel 11 "Modeller liknande digitala datorer" - han kallar räknaren för en "programdator". En färsk översikt finns hos van Emde Boas (1990). En nyligen genomförd behandling av Minsky (1961)/Lambek (1961) modellen kan hittas Boolos-Burgess-Jeffrey (2002); de reinkarnerar Lambeks "kulramsmodell" för att visa likvärdighet mellan Turing-maskiner och partiella rekursiva funktioner, och de ger en introduktion på forskarnivå till både abstrakta maskinmodeller (mot- och Turing-) och rekursionsteorins matematik. Från och med den första upplagan av Boolos-Burgess (1970) dök denna modell upp med praktiskt taget samma behandling.

Tidningarna : Tidningarna börjar med Wang (1957) och hans dramatiska förenkling av Turing-maskinen. Turing (1936), Kleene (1952), Davis (1958) och i synnerhet Post (1936) citeras i Wang (1957); i sin tur refereras Wang till av Melzak (1961), Minsky (1961) och Shepherdson–Sturgis (1961-3) då de oberoende reducerar Turing-banden till "diskar". Melzak (1961) förser sin rullstens-i-hål motmaskin modell med inriktning men för inte behandlingen vidare. Elgot–Robinsons (1964) arbete definierar RASP – de datorliknande maskiner med slumpmässig tillgång till lagrade program – och verkar vara de första som undersöker misslyckandet hos den avgränsade räknarmaskinen att beräkna mu-rekursiva funktioner . Detta misslyckande – förutom med den drakoniska användningen av Gödel-nummer på samma sätt som Minsky (1961)) leder till deras definition av "indexerade" instruktioner (dvs indirekt adressering) för deras RASP-modell. Elgot–Robinson (1964) och mer så Hartmanis (1971) undersöker RASP:er med självmodifierande program. Hartmanis (1971) specificerar en instruktionsuppsättning med inriktning, med hänvisning till föreläsningsanteckningar av Cook (1970). För användning i undersökningar av beräkningskomplexitet tillhandahåller Cook och hans doktorand Reckhow (1973) definitionen av ett RAM (deras modell och mnemoniska konvention liknar Melzaks, men ger honom ingen referens i tidningen). Pekarmaskinerna är en utlöpare av Knuth (1968, 1973) och oberoende Schönhage (1980).

För det mesta innehåller artiklarna matematik bortom grundnivån – i synnerhet de primitiva rekursiva funktionerna och mu-rekursiva funktionerna som presenteras elegant i Kleene (1952) och mindre på djupet, men ändå användbara, i Boolos-Burgess-Jeffrey (2002).

Alla texter och papper utom de fyra stjärnorna har bevittnats. Dessa fyra är skrivna på tyska och förekommer som referenser i Shepherdson–Sturgis (1963) och Elgot–Robinson (1964); Shepherdson–Sturgis (1963) ger en kort diskussion om deras resultat i Shepherdson–Sturgis Appendix A. Terminologin i åtminstone en artikel (Kaphengst (1959) tycks gå tillbaka till Burke-Goldstine-von Neumann (1946-7) analys av datorarkitektur.

Författare	År	Räknarmaskin	Bagge	Indirekt adressering	Självmodifierande program
Goldstine & von Neumann	1947
Kleene	1952
*Hermes	1954, 5	?
Wang	1957	tips		tips
*Peter	1958	?
Davis	1958
*Ershov	1959	?
*Kaphengst	1959	?
Melzak	1961				tips
Lambek	1961
Minsky	1961
Shepherdson & Sturgis	1963			tips
Elgot & Robinson	1964
Davis- Oavgörbart	1965
van Heijenoort	1967
Minsky	1967		tips	tips
Knuth	1968, 73
Hartmanis	1971
Cook & Reckhow	1973
Schonhage	1980
van Emde Boas	1990
Boolos & Burgess; Boolos, Burgess & Jeffrey	1970–2002

Anteckningar

Källor

George Boolos , John P. Burgess , Richard Jeffrey (2002), Computability and Logic: Fourth Edition , Cambridge University Press, Cambridge, England. Den ursprungliga Boolos-Jeffrey-texten har reviderats omfattande av Burgess: mer avancerad än en inledande lärobok. "Abacus machine"-modellen är omfattande utvecklad i kapitel 5 Abacus Computability ; det är en av tre modeller som behandlats och jämförs i stor utsträckning – Turing-maskinen (fortfarande i Boolos ursprungliga 4-tuppelform) och rekursion de andra två.
Arthur Burks , Herman Goldstine , John von Neumann (1946), "Preliminär diskussion om den logiska designen av ett elektroniskt datorinstrument", omtryckt s. 92ff i Gordon Bell och Allen Newell (1971), Computer Structures: Readings and Examples , McGraw- Hill Book Company, New York. ISBN 0-07-004357-4 .
Stephen A. Cook och Robert A. Reckhow (1972), Time-bounded random access machines , Journal of Computer Systems Science 7 (1973), 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 Languages", 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). Introduktion till automatteori, språk och beräkningar , 1:a uppl., Läsmassa: 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), Introduktion till metamatematik , 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. Se sidorna 462-463 där han definierar "en ny sorts abstrakt maskin eller 'automat' som behandlar sammanlänkade strukturer."
Lambek, Joachim (september 1961). "Hur man programmerar en oändlig kulram" . Kanadensisk matematisk bulletin . 4 (3): 295–302. doi : 10.4153/CMB-1961-032-6 . Manuskriptet mottogs av tidskriften den 15 juni 1961. I sitt bilaga II föreslår Lambek en "formell definition av "program". Han refererar till Melzak (1961) och Kleene (1952) Introduktion till metamatematik .
Melzak, ZA (september 1961). "En informell aritmetisk metod för beräkningsbarhet och beräkning" . Kanadensisk matematisk bulletin . 4 (3): 279–293. doi : 10.4153/CMB-1961-031-9 . Manuskriptet mottogs av tidskriften den 15 maj 1961. Melzak ger inga referenser men erkänner "fördelen med samtal med Drs. R. Hamming, D. McIlroy och V. Vyssots från Bell phone Laborators och med Dr. H. Wang vid Oxford University."
Minsky, Marvin (1961). "Rekursiv olöslighet av Posts problem med "Tag" och andra ämnen i teorin om Turing-maskiner". Annals of Mathematics . 74 (3): 437–455. doi : 10.2307/1970290 . JSTOR 1970290 .
Minsky, Marvin (1967). Beräkning: Finita och oändliga maskiner (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äkningsbarhet . I det förra kapitlet definierar han "Programmaskiner" och i det senare kapitlet diskuterar han "Universella programmaskiner med två register" och "...med ett register" osv.
John C. Shepherdson och HE Sturgis (1961) fick december 1961 "Computability of Recursive Functions", Journal of the Association of Computing Machinery (JACM) 10:217-255, 1963. Ett extremt värdefullt referensdokument. I sin Appendix 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.-Fys. Semesterberichte (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. Där Schōnhage visar motsvarigheten av sin SMM med "efterföljande RAM" (Random Access Machine), etc. resp. Storage Modification Machines , i Theoretical Computer Science (1979), s. 36–37
Peter van Emde Boas , "Machine Models and Simulations" s. 3–66, i: Jan van Leeuwen , ed. 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 förekommer på s. 32–35. Denna behandling förtydligar Schōnhage 1980 – den följer noga men utökar Schōnhage-behandlingen något. Båda referenserna kan behövas för effektiv förståelse.
Hao Wang (1957), "A Variant to Turing's Theory of Computing Machines", JACM ( Journal of the Association for Computing Machinery ) 4; 63–92. Framlagt vid föreningens möte 1954-06-23–25.

Wolfram, Stephen (2002). En ny typ av vetenskap . Wolfram Media, Inc. sid. 97-102 . ISBN 1-57955-008-8 .

externa länkar