Registrovat stroj - Register machine

V matematické logice a teoretické informatice je registrační stroj obecnou třídou abstraktních strojů používaných způsobem podobným Turingovu stroji . Všechny modely jsou ekvivalentní Turingovi .

Přehled

Registrační stroj získává své jméno podle použití jednoho nebo více „ registrů “. Na rozdíl od pásku a hlavy používaného Turingovým strojem model používá více, jednoznačně adresovaných registrů , z nichž každý obsahuje jedno kladné celé číslo .

V literatuře se nacházejí nejméně čtyři podtřídy, zde seřazené od nejprimitivnějších po nejpodobnější počítačům :

• Counter machine - nejprimitivnější a redukovaný teoretický model počítačového hardwaru. Chybí nepřímé adresování. Pokyny jsou v konečném automatu na způsob harvardské architektury .
• Pointer machine - kombinace modelů čítačů a RAM. Méně běžné a abstraktnější než oba modely. Pokyny jsou v konečném automatu na způsob harvardské architektury.
• Stroj s náhodným přístupem (RAM)-počítač s nepřímým adresováním a obvykle rozšířená sada instrukcí. Pokyny jsou v konečném automatu na způsob harvardské architektury.
• Model stroje s uloženým programem s náhodným přístupem (RASP)-RAM s instrukcemi ve svých registrech analogicky ke stroji Universal Turing ; jde tedy o příklad von Neumannovy architektury . Ale na rozdíl od počítače je model idealizován efektivně nekonečnými registry (a pokud jsou použity, efektivně nekonečnými speciálními registry, jako je akumulátor). Na rozdíl od počítače nebo dokonce RISC je počet instrukčních sad mnohem menší.

Jakýkoli správně definovaný model registrového stroje je Turingův ekvivalent . Výpočetní rychlost je velmi závislá na specifikách modelu.

V praktické informatice se někdy používá podobný koncept známý jako virtuální stroj k minimalizaci závislostí na základních architekturách strojů. Takové stroje se také používají pro výuku. Termín „registrační stroj“ je někdy používán k označení virtuálního stroje v učebnicích.

Formální definice

Registrační stroj se skládá z:

1. Neomezený počet označených, diskrétních, neomezených registrů neomezených rozsahem (kapacitou) : konečná (nebo v některých modelech nekonečná) sada registrů, z nichž každý je považován za nekonečný rozsah a každý z nich obsahuje jediné nezáporné celé číslo (0, 1, 2, ...). Registry mohou provádět svou vlastní aritmetiku, nebo může existovat jeden nebo více speciálních registrů, které provádějí aritmetiku, např. „Akumulátor“ a/nebo „registr adres“. Viz také stroj s náhodným přístupem .${\ displaystyle r_ {0} \ ldots r_ {n}}$
2. Počítadla shod nebo značky : diskrétní, nerozeznatelné objekty nebo značky pouze jednoho druhu vhodné pro model. V nejvíce redukovaném modelu počítacího stroje je za každou aritmetickou operaci přidán nebo odebrán pouze jeden objekt/značka z jeho umístění/pásky. U některých modelů čítačových strojů (např. Melzak (1961), Minsky (1961)) a většiny modelů RAM a RASP lze přidat nebo odebrat více než jeden objekt/značku v jedné operaci s „sčítáním“ a obvykle „odčítáním“; někdy s „násobením“ a/nebo „dělením“. Některé modely mají ovládací operace jako „kopírování“ (různě: „přesouvání“, „načítání“, „ukládání“), které přesouvají „shluky“ objektů/značek z registru do registru v rámci jedné akce.
3. A (velmi) omezený soubor instrukcí : instrukce se obvykle dělí na dvě třídy: aritmetiku a kontrolu. Pokyny jsou čerpány ze dvou tříd a vytvářejí „sady instrukcí“, takže sada instrukcí musí umožňovat, aby byl model Turingovým ekvivalentem (musí být schopen vypočítat jakoukoli částečnou rekurzivní funkci ).
   1. Aritmetika : aritmetické instrukce mohou fungovat na všech registrech nebo jen na speciálním registru (např. Akumulátoru). Jsou obvykle vybrány z následujících sad (ale výjimky přetékají):
      • Počitadlo: {Increment (r), Decrement (r), Clear-to-zero (r)}
      • Zmenšená RAM, RASP: {Increment (r), Decrement (r), Clear-to-zero (r), Load-okamžitá konstanta k, Add (r ₁ , r ₂ ), proper-Subtract (r ₁ , r ₂ ), Akumulátor přírůstku, Akumulátor dekrementu, Vymazat akumulátor, Přidat do obsahu akumulátoru registru r, správný-Odečíst obsah akumulátoru registru r,}
      • Rozšířená RAM, RASP: Všechny redukované instrukce plus: {Násobení, dělení, různé booleovské bitové operace (posun vlevo, bitový test atd.)}
   2. Ovládání :
      • Modely počítadel: volitelné {Kopírovat (r ₁ , r ₂ )}
      • Modely RAM a RASP: většina má {Kopírovat (r ₁ , r ₂ )} nebo {Načíst akumulátor od r, Uložit akumulátor do r, Načíst akumulátor s okamžitou konstantou}
      • Všechny modely: alespoň jeden podmíněný „skok“ (větev, přechod ) po testu registru, např. {Jump-if-zero, Jump-if-not-zero (tj. Jump-if-positive), Jump-if-equal, Skočit, pokud není rovno}
      • Všechny modely volitelné: {bezpodmínečný skok programu (goto)}
   3. Způsob adresování registrů :
      • Počítadlo: žádné nepřímé adresování, u vysoce atomizovaných modelů možné okamžité operandy
      • RAM a RASP: k dispozici nepřímé adresování, typické okamžité operandy
   4. Vstupní výstup : volitelný u všech modelů
4. Státní registr : Speciální instrukční registr „IR“, konečný a oddělený od výše uvedených registrů, ukládá aktuální instrukci, která má být provedena, a její adresu do TABULKY instrukcí; tento registr a jeho TABULKA jsou umístěny v konečném automatu.
   • IR je pro všechny modely zakázán. V případě paměti RAM a RASP může model pro účely určení „adresy“ registru vybrat buď (i) v případě přímého adresování - adresu uvedenou v tabulce a dočasně umístěnou v IR nebo ( ii) v případě nepřímého adresování - obsah registru specifikovaného instrukcí IR.
   • IR není "programový čítač" (PC) RASP (nebo konvenčního počítače). PC je jen další registr podobný akumulátoru, ale věnovaný uchovávání čísla aktuální instrukce RASP založené na registru. RASP má tedy dva registry "instrukce/program" - (i) IR (instrukční registr stroje konečného stavu) a (ii) PC ​​(programový čítač) pro program umístěný v registrech. (Stejně jako registr vyhrazený pro „PC“ může RASP věnovat další registr „Registru instrukcí programu“ (libovolný počet názvů, například „PIR,“ IR), „PR“ atd.)
5. Seznam označených pokynů, obvykle v pořadí : Konečný seznam pokynů . V případě počitadla, stroje s náhodným přístupem (RAM) a ukazatele je úložiště instrukcí v "TABULCE" stroje s konečným stavem; tyto modely jsou tedy příkladem harvardské architektury. V případě RASP je úložiště programů v registrech; toto je tedy příklad von Neumannovy architektury. Viz také stroj s náhodným přístupem a stroj s uloženým programem s náhodným přístupem. Pokyny jsou obvykle, stejně jako počítačové programy , seřazeny v postupném pořadí; pokud není skok úspěšný, pokračuje výchozí sekvence v číselném pořadí. Výjimkou jsou počítadla strojů počítadla (Lambek (1961), Minsky (1961)) - každá instrukce má alespoň jeden „další“ identifikátor instrukce „z“ a podmíněná větev má dva. ${\ displaystyle I_ {1} \ ldots I_ {m}}$
   
   • Všimněte si také, že model počítadla kombinuje dvě instrukce, JZ pak DEC: např. {INC (r, z), JZDEC (r, z _true , z _false )}.
     Viz McCarthy formalismu pro další informace o podmíněného výrazu "pokud r = 0, potom Z _platí ELSE z _falešné " (srov McCarthy (1960)).

Historický vývoj modelu registrového stroje

Počátkem 50. let se objevily dva trendy-první charakterizoval počítač jako Turingův stroj, druhý definoval počítačové modely-modely se sekvenčními instrukčními sekvencemi a podmíněnými skoky-s výkonem Turingova stroje, tj. Turingova ekvivalence. Potřeba této práce byla provedena v souvislosti se dvěma „tvrdými“ problémy: neřešitelným slovním problémem, který představuje Emil Post - jeho problém „tag“ - a velmi „tvrdý“ problém Hilbertových problémů - desátá otázka kolem diofantických rovnic . Výzkumníci pátrali po Turingově ekvivalentních modelech, které byly méně „logické“ povahy a více „aritmetické“ (srov Melzak (1961) s. 281, Shepherdson – Sturgis (1963) s. 218).

Zdá se, že první trend - k charakterizaci počítačů - pochází od Hanse Hermese (1954), Rózsa Pétera (1958) a Heinze Kaphengsta (1959), druhý trend u Hao Wanga (1954, 1957) a, jak bylo uvedeno výše, podpořil spolu s Zdzislaw Alexander Melzak (1961), Joachim Lambek (1961) a Marvin Minsky (1961, 1967).

Posledních pět jmen je výslovně uvedeno v uvedeném pořadí podle Jurije Matijajeviče . Navazuje na:

„Registrované stroje [někteří autoři používají„ registrační stroj “synonymní pro„ protipočítač “] jsou zvláště vhodné pro konstrukci diofantických rovnic. Stejně jako Turingovy stroje mají velmi primitivní instrukce a navíc se zabývají čísly“ (Yuri Matiyasevich ( 1993), Hilbertův desátý problém , komentář ke kapitole 5 knihy, na adrese http://logic.pdmi.ras.ru/yumat/H10Pbook/commch_5htm .)

Zdá se, že Lambek, Melzak, Minsky a Shepherdson a Sturgis nezávisle očekávali stejnou myšlenku současně. Viz Poznámka o přednostech níže.

Historie začíná Wangovým modelem.

Wangův (1954, 1957) model: Post -Turingův stroj

Wang práce vyplýval z Emil Post (1936) papíru a vedl Wang k jeho definici jeho Wang B-stroj -a dvou symbolů Post-Turingova stroje výpočetním modelu s pouhými čtyřmi atomovými instrukcí:

{LEFT, RIGHT, PRINT, JUMP_if_marked_to_instruction_z}

K těmto čtyřem přidali Wang (1954, 1957) a poté CY Lee (1961) další instrukci ze sady příspěvků {ERASE} a poté bezpodmínečný skok Postu {JUMP_to_ instruction_z} (nebo aby to bylo jednodušší, podmíněný skok JUMP_IF_blank_to_instruction_z, nebo obojí. Lee to pojmenoval jako model „W-machine“:

{LEFT, RIGHT, PRINT, ERASE, JUMP_if_marked, [might JUMP or JUMP_IF_blank]}

Wang vyjádřil naději, že jeho model bude „sblížením“ (str. 63) mezi teorií Turingových strojů a praktickým světem počítače.

Wangova práce byla velmi vlivná. Nalezneme jej, na kterého se odkazují Minsky (1961) a (1967), Melzak (1961), Shepherdson a Sturgis (1963). Shepherdson a Sturgis (1963) skutečně poznamenávají, že:

„... pokusili jsme se posunout o krok dále„ sbližování “mezi praktickými a teoretickými aspekty výpočtu navrhovanými Wangem“ (str. 218)

Martin Davis nakonec vyvinul tento model do (2-znakového) post-Turingova stroje.

Obtíže s modelem Wang/Post – Turing :

Až na to, že nastal problém: model Wang (šest instrukcí stroje se 7 instrukcemi Post – Turingova stroje) byl stále jednovrstvým Turingovým zařízením, jakkoli hezký mohl být postupný instrukční tok programu . Jak Melzak (1961), tak Shepherdson a Sturgis (1963) to pozorovali (v kontextu určitých důkazů a vyšetřování):

"... Turingův stroj má určitou neprůhlednost ... Turingův stroj je v (hypotetickém) provozu pomalý a obvykle komplikovaný. Z toho důvodu je poměrně obtížné jej navrhnout a ještě obtížněji zkoumat takové záležitosti, jako je čas nebo skladování." optimalizace nebo srovnání účinnosti dvou algoritmů. (Melzak (1961) s. 281)

„... i když to není obtížné ... důkazy jsou komplikované a únavné sledovat ze dvou důvodů: (1) Turingův stroj má pouze hlavu, takže je člověk povinen rozdělit výpočet na velmi malé kroky operací na jedné číslici . (2) Má pouze jednu pásku, takže se člověk musí potýkat s problémem, aby našel číslo, na kterém chce pracovat, a udržel jej oddělené od ostatních čísel “(Shepherdson a Sturgis (1963) s. 218).

Skutečně, jak ukazují příklady na příkladech Turingových strojů , Post -Turingových strojů a částečných funkcí , práce může být „komplikovaná“.

Modely Minsky, Melzak-Lambek a Shepherdson – Sturgis „přestřihly pásku“ do mnoha

Proč tedy „nepřestřihnout pásku“, aby každá byla nekonečně dlouhá (aby se do ní vešlo celé číslo jakékoli velikosti), ale měla levý konec a tyto tři pásky nazvala „pásky typu Post – Turing (tj. Podobné Wangovi“)? Jednotlivé hlavy se budou pohybovat doleva (pro snížení) a doprava (pro přírůstek). V jednom smyslu hlavy označují „vrcholy hromádky“ zřetězených značek. Nebo v Minsky (1961) a Hopcroft a Ullman (1979, s. 171 a dále) je páska vždy prázdná, kromě značky na levém konci - hlava nikdy nevytiskne ani nevymaže.

Jen musíme dávat pozor, abychom naše instrukce napsali tak, aby došlo k testu na nulu a ke skoku, než dojde ke snížení, jinak náš stroj „spadne z konce“ nebo „narazí na konec“-budeme mít příklad částečného funkce. Před snížením musí náš stroj vždy položit otázku: „Je páska/čítač prázdná? Pokud ano, nemohu dekrementovat, jinak mohu.“

Příklad (ne) správného odčítání najdete v části Dílčí funkce .

Minsky (1961) a Shepherdson – Sturgis (1963) dokazují, že jen několik pásek- jen jeden jako jeden- stále umožňuje stroji být Turingovým ekvivalentem, pokud jsou data na pásce reprezentována Gödelovým číslem (nebo nějakým jiným jednoznačně kódovatelným- dekódovatelné číslo); toto číslo se bude vyvíjet v průběhu výpočtu. Ve verzi s jednou páskou s kódováním Gödelova čísla musí být počitadlo schopné (i) vynásobit Gödelovo číslo konstantou (čísla "2" nebo "3") a (ii) dělit konstantou (čísla "2" nebo „3“) a přeskočte, pokud je zbytek nula. Minsky (1967) ukazuje, že potřebu této bizarní instrukční sady lze zmírnit na {INC (r), JZDEC (r, z)} a praktické pokyny {CLR (r), J (r)}, pokud jsou k dispozici dvě kazety . Stále je však nutná jednoduchá gödelizace. Podobný výsledek se objevuje v Elgot – Robinson (1964) s ohledem na jejich model RASP.

Melzakův (1961) model je jiný: shluky oblázků jdou do děr a ven

Melzakův (1961) model je výrazně odlišný. Vzal si svůj vlastní model, převrátil pásky svisle a nazval je „díry v zemi“, aby byly vyplněny „oblázky“. Na rozdíl od „přírůstku“ a „snižování“ Minskyho Melzak umožňoval řádné odečítání jakéhokoli počtu oblázků a „přidává“ jakýkoli počet oblázků.

Pro svůj model definuje nepřímé adresování (str. 288) a uvádí dva příklady jeho použití (str. 89); jeho „důkaz“ (s. 290–292), že jeho model je Turingovým ekvivalentem, je tak útržkovitý, že čtenář nemůže říci, zda zamýšlel nepřímé adresování jako požadavek na důkaz.

Dědictvím Melzakova modelu je Lambkovo zjednodušení a znovuobjevení jeho mnemotechnických konvencí v Cook a Reckhow 1973.

Lambek (1961) atomizuje Melzakův model na model Minsky (1961): INC a DEC-with-test

Lambek (1961) vzal Melzakův ternární model a atomizoval jej podle dvou unárních instrukcí- X+, X- pokud možno ještě skok- přesně stejných dvou, jaké vymyslel Minsky (1961).

Nicméně, stejně jako model Minsky (1961), model Lambek provádí své instrukce standardně sekvenčním způsobem- X+ i X- nesou identifikátor další instrukce a X- také nese instrukci jump-to, pokud je nula -test je úspěšný.

Elgot – Robinson (1964) a problém RASP bez nepřímého adresování

Stroj s uloženým programem RASP nebo náhodným přístupem začíná jako počítač čítačů s „programem instrukce“ umístěným ve svých „registrech“. Analogický, ale nezávislý na „instrukčním registru“ konečného stavu stroje, alespoň jeden z registrů (přezdívaný „programový čítač“ (PC)) a jeden nebo více „dočasných“ registrů uchovávají záznam a fungují na číslo aktuální instrukce. TABULKA instrukcí stroje konečného stavu je zodpovědná za (i) načítání aktuální programové instrukce ze správného registru, (ii) analýzu programové instrukce, (iii) načítání operandů specifikovaných programovou instrukcí a (iv) provádění programové instrukce .

Až na to, že je tu problém: Pokud je počítačový podvozek na bázi šasi čítače , nebude von Neumannův stroj Turingovým ekvivalentem. Nelze vypočítat vše, co lze vypočítat. Model je ze své podstaty ohraničen velikostí pokynů svého (velmi) konečného stavu stroje. RASP založený na počítačích může vypočítat jakoukoli primitivní rekurzivní funkci (např. Násobení), ale ne všechny rekurzivní funkce mu (např. Funkce Ackermann ).

Elgot – Robinson prozkoumal možnost umožnit jejich modelu RASP „vlastní úpravu“ jeho programových pokynů. Myšlenka byla stará, navržená Burksem-Goldstinem-von Neumannem (1946-7) a někdy se jí říkalo „vypočítané goto“. Melzak (1961) konkrétně zmiňuje „vypočítané goto“ jménem, ​​ale místo toho poskytuje svému modelu nepřímé adresování.

Vypočítaný goto: rašple programu pokynů, které upravuje „goto adresa“ v conditional- nebo nepodmíněný skok programu výuky.

Ale to problém nevyřeší (pokud se člověk neuchýlí k číslům Gödel ). Co je nutné, je metoda pro načtení adresy programové instrukce, která leží (daleko) „za/nad“ horní hranicí registru instrukcí a TABLE konečného stavu stroje.

Příklad: Počítadlo vybavené pouze čtyřmi neomezenými registry může např. Znásobit libovolná dvě čísla (m, n) dohromady za vzniku p - a tedy být primitivní rekurzivní funkcí - bez ohledu na to, jak velká jsou čísla m a n; k tomu je navíc zapotřebí méně než 20 pokynů! např. {1: CLR (p), 2: JZ (m, hotovo), 3 vnější_smyčka: JZ (n, hotovo), 4: CPY (m, teplota), 5: vnitřní_smyčka: JZ (m, vnější_smyčka), 6: DEC (m), 7: INC (p), 8: J (vnitřní_smyčka), 9: vnější_smyčka: DEC (n), 10 J (vnější_smyčka), HALT}

S pouhými 4 registry však tento stroj není dostatečně velký na to, aby vytvořil RASP, který může spustit multiplikační algoritmus jako program . Bez ohledu na to, jak velký svůj konečný stavový automat postavíme, vždy bude existovat program (včetně jeho parametrů), který je větší. Takže podle definice nemůže být ohraničený programový stroj, který nepoužívá neomezené kódovací triky, jako jsou čísla Gödel, univerzální .

Minsky (1967) naznačuje problém ve svém vyšetřování pultového stroje (říká mu „programové počítačové modely“) vybaveného instrukcemi {CLR (r), INC (r) a RPT („a“ krát instrukce m až n)}. Neříká nám, jak problém vyřešit, ale pozoruje, že:

"... počítač s programem musí mít nějaký způsob, jak sledovat, kolik RPT zbývá udělat, a to by mohlo vyčerpat konkrétní množství paměti povolené v konečné části počítače. Operace RPT vyžadují vlastní nekonečné registry „Obecně s nimi musí být zacházeno odlišně od ostatních druhů operací, které jsme zvažovali.“ (str. 214)

Elgot a Robinson ale problém řeší: Rozšiřují svůj P ₀ RASP o indexovanou sadu instrukcí - poněkud komplikovanější (ale flexibilnější) forma nepřímého adresování. Jejich model P ' ₀ adresuje registry přidáním obsahu „základního“ registru (specifikovaného v instrukci) do „indexu“ uvedeného výslovně v instrukci (nebo naopak, prohození „základny“ a „indexu“). Instrukce indexování P ' ₀ mají tedy ještě jeden parametr než neindexování instrukcí P ₀ :

Příklad: INC (r _base , index); efektivní adresa bude [r _base ] + index, kde „index“ přirozeného čísla je odvozen od samotné instrukce stroje s konečným stavem.

Hartmanis (1971)

V roce 1971 Hartmanis zjednodušil indexování na indirection pro použití v jeho modelu RASP.

Nepřímé adresování: Registr ukazatelů dodává stroji konečného stavu adresu cílového registru požadovaného pro instrukci. Jinak řečeno: Na obsah tohoto ukazatele-registr je adresa na „cíl“ zaregistrovat které mají být použity podle instrukcí. Pokud je registr ukazatele neomezený, bude RAM a vhodný RASP postavený na jeho šasi ekvivalentní Turingovi. Cílový registr může sloužit buď jako zdrojový nebo cílový registr, jak je uvedeno v instrukci.

Všimněte si toho, že počítač konečného stavu nemusí explicitně specifikovat adresu tohoto cílového registru. To jen říká zbytku stroje: Získejte mi obsah registru, na který ukazuje můj ukazatel ukazatele, a pak s ním proveďte xyz. Musí specifikovat výslovně jménem, ​​prostřednictvím své instrukce, tento registr ukazatelů (např. „N“ nebo „72“ nebo „PC“ atd.), Ale nemusí vědět, jaké číslo registr ukazatele ve skutečnosti obsahuje ( možná 279 431).

Cook and Reckhow (1973) popisují RAM

Cook a Reckhow (1973) citují Hartmanise (1971) a zjednodušují jeho model na to, čemu říkají stroj s náhodným přístupem (RAM-tj. Stroj s indirection a harvardskou architekturou). V jistém smyslu jsme zpět k Melzakovi (1961), ale s mnohem jednodušším modelem než Melzakův.

Přednost

Minsky pracoval v Lincolnově laboratoři MIT a publikoval zde svou práci; jeho papír byl přijat k publikování v Annals of Mathematics 15. srpna 1960, ale vyšel až v listopadu 1961. Zatímco k přijetí došlo celý rok před přijetím a zveřejněním díla Melzaka a Lambka (přijato, respektive 15. května a 15. června) , 1961, a publikováno vedle sebe v září 1961). Že (i) oba byli Kanaďané a publikováni v Kanadském matematickém bulletinu , (ii) ani jeden by neměl odkaz na Minského dílo, protože ještě nebyl publikován v recenzovaném časopise, ale (iii) Melzak odkazuje na Wang a Lambek odkazy Melzak, vede člověka k hypotéze, že jejich práce probíhala současně a nezávisle.

Téměř přesně totéž se stalo Shepherdsonovi a Sturgisovi. Jejich papír byl přijat v prosinci 1961 - jen několik měsíců po přijetí díla Melzaka a Lambeka. Znovu měli malý (maximálně 1 měsíc) nebo žádný prospěch z přezkoumání práce Minského. Dbali na to, aby v poznámkách pod čarou pozorovali, že papíry od Ershov, Kaphengst a Peter se „nedávno objevily“ (str. 219). Ty byly publikovány mnohem dříve, ale objevily se v německém jazyce v německých časopisech, takže se objevily problémy s přístupností.

Závěrečná práce Shepherdsona a Sturgise se objevila v recenzovaném časopise až v roce 1963. A jak spravedlivě a poctivě poznamenávají ve svém dodatku A, „systémy“ Kaphengst (1959), Ershov (1958), Peter (1958) jsou všechny tak podobné výsledkům, které byly získány později, a jsou nerozeznatelné pro sadu následujících:

produkovat 0 tj. 0 → n

zvýšit číslo, tj. n+1 → n

„tj. provádění operací, které generují přirozená čísla“ (str. 246)

zkopírujte číslo, tj. n → m

„změnit průběh výpočtu“ buď porovnáním dvou čísel, nebo snížením na 0

Shepherson a Sturgis skutečně uzavírají

„Různé minimální systémy jsou si velmi podobné“ (str. 246)

Podle data vydání byly prvními díly Kaphengst (1959), Ershov (1958), Peter (1958).

Viz také

Bibliografie

Podkladové texty: Následující bibliografie pramenných prací obsahuje řadu textů, které mají být použity jako podklad. Matematiku, která v padesátých a šedesátých letech minulého století vedla k záplavě papírů o abstraktních strojích, lze nalézt ve van Heijenoort (1967) - soubor původních prací pokrývajících 50 let od Frege (1879) do Gödel (1931). Davis (ed.) Undecidable (1965) nese pochodeň kupředu počínaje Gödelem (1931) přes Gödelovo (1964) postscriptum (str. 71); původní dokumenty Alana Turinga (1936-7) a Emila Posta (1936) jsou obsaženy v knize The Undecidable . Matematika Church, Rosser a Kleene, která se objevuje jako dotisky původních prací v knize The Undecidable, je dále uvedena v Kleene (1952), povinném textu pro každého, kdo usiluje o hlubší porozumění matematice za stroji. Kleene (1952) a Davis (1958) jsou odkazovány v řadě článků.

Správné zacházení s počitadlem najdete v kapitole 11 Minskyho (1967) „Modely podobné digitálním počítačům“ - počítač pultů nazývá „programovací počítač“. Nedávný přehled je k dispozici u van Emde Boas (1990). Nedávné zpracování modelu Minsky (1961)/Lambek (1961) lze nalézt Boolos-Burgess-Jeffrey (2002); reinkarnují Lambkův „abakusový model“, aby prokázali ekvivalenci Turingových strojů a částečných rekurzivních funkcí, a poskytují úvod na úrovni absolventů jak k abstraktním modelům strojů (proti- a Turingovým), tak k matematice rekurzivní teorie. Počínaje prvním vydáním Boolos-Burgess (1970) se tento model objevil s prakticky stejným zacházením.

Noviny : Listy začínají Wangem (1957) a jeho dramatickým zjednodušením Turingova stroje. Turing (1936), Kleene (1952), Davis (1958) a zejména Post (1936) jsou citováni ve Wang (1957); zase na Wanga odkazují Melzak (1961), Minsky (1961) a Shepherdson – Sturgis (1961-3), protože nezávisle redukují Turingovy pásky na „pulty“. Melzak (1961) poskytuje svému modelu pultu s oblázky v dírkách indirekci, ale dále nenese léčbu. Práce Elgot – Robinson (1964) definují RASP-počítače podobné počítačům s uloženým programem s náhodným přístupem a vypadají jako první, kdo zkoumal selhání stroje s omezeným čítačem při výpočtu mu-rekurzivních funkcí. Toto selhání - kromě drakonického používání Gödelových čísel způsobem Minskyho (1961) - vede k jejich definici „indexovaných“ instrukcí (tj. Nepřímého adresování) pro jejich model RASP. Elgot – Robinson (1964) a další Hartmanis (1971) zkoumají RASP se samočinně se měnícími programy. Hartmanis (1971) specifikuje instrukční sadu s indirection, cituje poznámky z přednášek o Cookovi (1970). Pro použití při vyšetřování výpočetní složitosti Cook a jeho postgraduální student Reckhow (1973) poskytují definici RAM (jejich model a mnemotechnická konvence jsou podobné jako u Melzaka, ale nenabízejí mu žádnou referenci v příspěvku). Ukazovátka jsou odnožou Knutha (1968, 1973) a nezávisle Schönhage (1980).

Příspěvky z větší části obsahují matematiku přesahující bakalářský stupeň-zejména primitivní rekurzivní funkce a rekurzivní funkce mu prezentované elegantně v Kleene (1952) a méně do hloubky, ale přesto užitečné, v Boolos-Burgess-Jeffrey (2002).

Všechny texty a dokumenty kromě čtyř hvězd byly svědky. Tyto čtyři jsou psány v němčině a objevují se jako reference v Shepherdson – Sturgis (1963) a Elgot – Robinson (1964); Shepherdson – Sturgis (1963) nabízí krátkou diskusi o svých výsledcích v příloze A. analýza počítačové architektury.

Autor	Rok	Odkaz	Turingův stroj	Počítadlo	RAM	RAŠPLE	Ukazovací stroj	Nepřímé adresování	Samoobslužný program
Goldstine & von Neumann	1947
Kleene	1952
*Hermes	1954, 5			?
Wang	1957			rady				rady
*Petr	1958			?
Davise	1958
*Ershov	1959			?
*Kaphengst	1959			?
Melzak	1961								rady
Lambek	1961
Minský	1961
Shepherdson & Sturgis	1963							rady
Elgot & Robinson	1964
Davis- nerozhodnutelný	1965
van Heijenoort	1967
Minský	1967				rady			rady
Knuth	1968, 73
Hartmanis	1971
Cook & Reckhow	1973
Schonhage	1980
van Emde Boas	1990
Boolos & Burgess; Boolos, Burgess a Jeffrey	1970–2002

Reference

Poznámky

Zdroje

• Wolfram, Stephen (2002). Nový druh vědy . Wolfram Media, Inc., s.  97-102 . ISBN 1-57955-008-8.

externí odkazy

• Weisstein, Eric W. „Registrační stroj“ . MathWorld .
• Igblan - Minsky Register Machines