Direktzugriffsmaschine - Random-access machine

In der Informatik ist Random Access Machine ( RAM ) eine abstrakte Maschine in der allgemeinen Klasse der Registermaschinen . Der RAM ist sehr ähnlich den Zähler Maschine aber mit der zusätzlichen Fähigkeit , ‚indirekte Adressierung‘ sein Registers. Wie die Zählermaschine hat der RAM seine Befehle im endlichen Teil der Maschine (der sogenannten Harvard-Architektur ).

Das RAM-Äquivalent der universellen Turing-Maschine  – mit ihrem Programm in den Registern sowie ihren Daten – wird als Random-Access-Speicherprogrammmaschine oder RASP bezeichnet. Es ist ein Beispiel für die sogenannte von Neumann-Architektur und kommt dem gängigen Computerbegriff am nächsten .

Zusammen mit den Turing-Maschinen- und Gegenmaschinenmodellen werden die RAM- und RASP-Modelle für die Berechnung der Komplexitätsanalyse verwendet . Van Emde Boas (1990) nennt diese drei Plus- Pointer-Machine- Modelle "sequentielle Maschine", um sie von " Parallel-Random-Access-Machine "-Modellen zu unterscheiden.

Einführung in das Modell

Das Konzept einer Random-Access- Maschine (RAM) beginnt mit dem einfachsten Modell von allen, dem sogenannten Counter-Machine- Modell. Zwei Zusätze rücken ihn jedoch von der Thekenmaschine weg. Die erste erweitert die Maschine um den Komfort der indirekten Adressierung; die zweite verschiebt das Modell in Richtung des konventionelleren Akkumulator-basierten Computers mit dem Hinzufügen eines oder mehrerer (dedizierter) Hilfsregister, von denen das gebräuchlichste "der Akkumulator" genannt wird.

Formale Definition

Eine Maschine mit wahlfreiem Zugriff (RAM) ist ein abstraktes Rechenmaschinenmodell, das mit einer Mehrregister- Zählermaschine mit dem Zusatz einer indirekten Adressierung identisch ist . Nach Ermessen eines Befehls aus der TABLE seiner endlichen Automaten leitet der Automat die Adresse eines "Ziel"-Registers entweder (i) direkt aus dem Befehl selbst oder (ii) indirekt aus dem Inhalt (z "Zeiger"-Register, das in der Anweisung angegeben ist.

Per Definition: Ein Register ist ein Ort mit sowohl einer Adresse (einer eindeutigen, unterscheidbaren Bezeichnung/Lokator, die einer natürlichen Zahl entspricht) als auch einem Inhalt  – einer einzelnen natürlichen Zahl. Aus Gründen der Genauigkeit verwenden wir die quasi-formale Symbolik von Boolos-Burgess-Jeffrey (2002), um ein Register, seinen Inhalt und eine Operation auf einem Register zu spezifizieren:

• [r] bedeutet "der Inhalt des Registers mit der Adresse r". Das Label "r" ist hier eine "Variable", die mit einer natürlichen Zahl oder einem Buchstaben (zB "A") oder einem Namen gefüllt werden kann.
• → bedeutet „kopieren/einzahlen in“ oder „ersetzt“, aber ohne Zerstörung der Quelle

Beispiel: [3] +1 → 3; bedeutet "Der Inhalt des Quellregisters mit der Adresse "3" plus 1 wird in das Zielregister mit der Adresse "3" gelegt (hier sind Quelle und Ziel an der gleichen Stelle). Wenn [3]=37, also der Inhalt von Register 3 ist die Zahl "37", dann wird 37+1 = 38 in Register 3 eingetragen.

Beispiel: [3] → 5; bedeutet "Der Inhalt des Quellregisters mit der Adresse "3" wird in das Zielregister mit der Adresse "5" übertragen. Wenn [3]=38, dh der Inhalt von Register 3 ist die Nummer 38, dann wird diese Nummer in das Register 5. Der Inhalt von Register 3 wird durch diese Operation nicht gestört, daher bleibt [3] weiterhin 38, jetzt gleich wie [5].

Definition: Ein direkter Befehl gibt im Befehl selbst die Adresse des Quell- oder Zielregisters an, dessen Inhalt Gegenstand des Befehls ist. Definition: Ein indirekter Befehl ist ein Befehl , der ein "Zeigerregister" spezifiziert, dessen Inhalt die Adresse eines "Ziel"-Registers ist. Das Zielregister kann entweder eine Quelle oder ein Ziel sein (die verschiedenen COPY-Befehle liefern Beispiele dafür). Ein Register kann sich indirekt selbst adressieren.

In Ermangelung einer Norm/Konvention wird in diesem Artikel "direkt/indirekt", abgekürzt als "d/i", als Parameter (oder Parameter) in der Anweisung angegeben:

Beispiel: COPY ( d , A, i Mittel, N) direkt d die Adresse des bekommen Quellregister selbst aus dem Befehls ( "A" Register) , sondern indirekt i die Zieladresse vom Lesezeiger-Register N. Angenommen , [N] = 3, dann ist Register 3 das Ziel und der Befehl führt Folgendes aus: [A] → 3.

Definition: Der Inhalt des Quellregisters wird von der Anweisung verwendet. Die Adresse des Quellregisters kann entweder (i) direkt durch den Befehl oder (ii) indirekt durch das durch den Befehl angegebene Zeigerregister angegeben werden.

Definition: Der Inhalt des Zeigerregisters ist die Adresse des "Ziel"-Registers.

Definition: Der Inhalt des Zeigerregisters zeigt auf das Zielregister  – das "Ziel" kann entweder ein Quell- oder ein Zielregister sein.

Definition: Im Zielregister legt der Befehl sein Ergebnis ab. Die Adresse des Quellregisters kann entweder (i) direkt durch den Befehl oder (ii) indirekt durch das durch den Befehl angegebene Zeigerregister angegeben werden. Die Quell- und Zielregister können eins sein.

Refresher: Das Gegenmaschinenmodell

Melzak (1961) bietet eine einfache Visualisierung einer Gegenmaschine: Ihre "Register" sind Löcher im Boden, und diese Löcher halten Kieselsteine. Nach einer Anweisung fügt "der Computer" (Person oder Maschine) in diese Löcher hinein und aus diesen heraus (INCrements) oder entfernt (DECrements) einen einzelnen Kieselstein. Nach Bedarf kommen zusätzliche Kieselsteine ​​aus einem unendlichen Vorrat und überschüssige Kieselsteine ​​gehen zurück; Wenn das Loch zu klein ist, um die Kieselsteine ​​​​unterzubringen, gräbt der "Computer" das Loch größer.

Minsky (1961) und Hopcroft-Ullman 1979 (S. 171) bieten die Visualisierung einer Multi-Tape- Turing-Maschine mit so vielen linksseitigen Bändern wie "Registern". Die Länge jedes Bandes ist nach rechts unbegrenzt, und jedes Quadrat ist leer, mit Ausnahme des linken Endes, das markiert ist. Der Abstand des "Kopfes" eines Bandes von seinem linken Ende, gemessen in Bandquadraten, stellt die natürliche Zahl im "Register" dar. Um die Anzahl der Quadrate zu verringern, bewegt sich der Tonkopf nach links; Erhöhen Sie es nach rechts. Es ist nicht erforderlich, Markierungen auf dem Band zu drucken oder zu löschen; die einzigen bedingten Anweisungen bestehen darin, zu überprüfen, ob sich der Kopf am linken Ende befindet, indem eine Markierung für das linke Ende mit einer "Sprung-wenn-markiert-Anweisung" getestet wird.

Die folgenden Anweisungen "mnemonics" zB "CLR (r)" sind willkürlich; keine Norm existiert.

Die Registermaschine hat für einen Speicher außerhalb ihres endlichen Automaten – eine unbegrenzte (vgl. Fußnote|zählbare und unbegrenzte) Sammlung von diskreten und eindeutig gekennzeichneten Orten mit unbegrenzter Kapazität, die "Register" genannt werden. Diese Register enthalten nur natürliche Zahlen (Null und die positiven ganzen Zahlen). Gemäß einer Liste von sequentiellen Befehlen in der TABELLE des endlichen Automaten arbeiten einige (z. B. 2) Typen von primitiven Operationen auf den Inhalten dieser "Register". Schließlich steht ein Bedingungsausdruck in Form eines IF-THEN-ELSE zur Verfügung, um den Inhalt von einem oder zwei Registern zu testen und den endlichen Automaten aus der voreingestellten Befehlssequenz zu "verzweigen/zu springen".

Basismodell 1 : Das Modell, das Minskys (1961) Visualisierung und Lambek (1961) am nächsten kommt:

• { Inhalt von Register r inkrementieren, Inhalt von Register r dekrementieren, WENN Inhalt von Register r Null ist DANN Sprung zum Befehl I _z ELSE weiter zum nächsten Befehl }:

Anweisung	Gedächtnisstütze	Aktion bei Register(n) "r"	Aktion auf dem Befehlsregister der endlichen Zustandsmaschine, IR
Zuwachs	INC ( r )	[r] + 1 → r	[IR] + 1 → IR
DEkrementieren	DEZ ( r )	[r] - 1 → r	[IR] + 1 → IR
Springen, wenn Null	JZ ( r, z )	keiner	WENN [r] = 0 DANN z → IR ELSE [IR] + 1 → IR
Halt	h	keiner	[IR] → IR

Basismodell 2 : Das „Nachfolger“-Modell (benannt nach der Nachfolgefunktion der Peano-Axiome ):

• { Erhöhe den Inhalt von Register r, CLeaR den Inhalt von Register r, IF Inhalt von Register r _j Entspricht dem Inhalt von Register r _k THEN Springe zur Anweisung I _z ELSE gehe zur nächsten Anweisung }

Anweisung	Gedächtnisstütze	Aktion bei Register(n) "r"	Aktion auf dem Befehlsregister der endlichen Zustandsmaschine, IR
Klar	CLR ( r )	0 → r	[IR] + 1 → IR
Zuwachs	INC ( r )	[r] + 1 → r	[IR] + 1 → IR
Springen wenn gleich	JE (r1, r2, z)	keiner	WENN [r1] = [r2] DANN z → IR ELSE [IR] + 1 → IR
Halt	h	keiner	[IR] → IR

Basismodell 3 : Verwendet von Elgot-Robinson (1964) bei ihrer Untersuchung von begrenzten und unbegrenzten RASPs – das "Nachfolger"-Modell mit COPY anstelle von CLEAR:

• { INkrementiere den Inhalt von Register r, COPY den Inhalt von Register r _j in Register r _k , WENN Inhalt von Register r _j Entspricht dem Inhalt von Register r _k dann Springe zur Anweisung I _z ELSE gehe zur nächsten Anweisung }

Anweisung	Gedächtnisstütze	Aktion bei Register(n) "r"	Aktion auf dem Befehlsregister der endlichen Zustandsmaschine, IR
KOPIEREN	KOPIEREN (r1, r2)	[r1] → r2	[IR] + 1 → IR
Zuwachs	INC ( r )	[r] + 1 → r	[IR] + 1 → IR
Springen wenn gleich	JE (r1, r2, z)	keiner	WENN [r1] = [r2] DANN z → IR ELSE [IR] + 1 → IR
Halt	h	keiner	[IR] → IR

Erstellen von "Komfortanleitungen" aus den Basissets

Die drei obigen Basissätze 1, 2 oder 3 sind insofern äquivalent, als man die Anweisungen eines Satzes mit den Anweisungen eines anderen Satzes erzeugen kann (eine interessante Übung: ein Hinweis von Minsky (1967) – deklarieren Sie ein reserviertes Register, z es "0" (oder Z für "Null" oder E für "Löschen"), um die Zahl 0 zu enthalten). Die Wahl des Modells hängt davon ab, welches der Autor für eine Demonstration oder einen Beweis usw. am einfachsten zu verwenden ist.

Darüber hinaus können wir aus den Basismengen 1, 2 oder 3 jede der primitiven rekursiven Funktionen erstellen ( vgl. Minsky (1967), Boolos-Burgess-Jeffrey (2002) ). (Wie man das Netz weiter ausbreitet, um die totalen und partiellen mu-rekursiven Funktionen zu erfassen, wird im Zusammenhang mit der indirekten Adressierung diskutiert). Das Erstellen der primitiven rekursiven Funktionen ist jedoch schwierig, weil die Befehlssätze so ... primitiv (klein) sind. Eine Lösung besteht darin, ein bestimmtes Set mit "Komfortanleitungen" aus einem anderen Set zu erweitern:

Diese werden nicht Subroutinen im herkömmlichen Sinne , sondern Blöcke von Befehlen aus dem Basissatz erstellt und eine mnemonic gegeben. Um diese Blöcke formal zu verwenden, müssen wir sie entweder (i) in ihre Basisbefehls-Äquivalente „erweitern“ – sie erfordern die Verwendung von temporären oder „Hilfs“-Registern, sodass das Modell dies berücksichtigen muss, oder ( ii) Entwerfen Sie unsere Maschinen/Modelle mit den Anweisungen „eingebaut“.

Beispiel: Basissatz 1. Um CLR (r) zu erstellen, verwenden Sie den Befehlsblock, um das Register r auf Null herunterzuzählen. Beachten Sie die Verwendung des oben genannten Hinweises:

• CLR (r) = _Äquiv.
• Schleife : JZ (r, Ausgang )

• DEZ (r)
• JZ (0, Schleife )

• Ausgang : usw.

Auch hier dient all dies nur der Bequemlichkeit; nichts davon erhöht die intrinsische Kraft des Modells.

Zum Beispiel: Der am stärksten erweiterte Satz würde jede einzelne Anweisung aus den drei Sätzen enthalten, plus unbedingten Sprung J (z), dh:

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

Die meisten Autoren wählen den einen oder anderen der bedingten Sprünge, z. B. verwenden Shepherdson-Sturgis (1963) die obige Menge minus JE (um genau zu sein, verwenden sie JNZ – Jump if Not Zero anstelle von JZ; eine weitere mögliche Bequemlichkeitsanweisung).

Die "indirekte" Operation

Beispiel für indirekte Adressierung

In unserem täglichen Leben ist die Vorstellung einer "indirekten Operation" nicht ungewöhnlich.

Beispiel: Eine Schatzsuche.

Am Standort "Tom_&_Becky's_cave_in_pirate_chest" finden wir eine Karte, die uns zum "Schatz" führt:

(1) Wir gehen zum Ort "Tom_&_Becky's_cave..." und graben herum, bis wir eine Holzkiste finden

(2) In der Kiste befindet sich eine Karte zum Fundort des Schatzes: "under_Thatcher's_front_porch"

(3) Wir gehen zum Ort "under_Thatcher's_front_porch", hämmern den Beton weg und entdecken "den Schatz": einen Sack rostiger Türklinken.

Indirektion spezifiziert eine Stelle wie der Piraten - Kasten identifiziert in „Tom _ & _ Becky's_cave ...“, die als wirkt Zeiger zu einem anderen Ort (einschließlich sich selbst): der Inhalt (die Schatzkarte) liefert die „Adresse“ des Ziel location „under_Thatcher 's_front_porch", wo die eigentliche Aktion stattfindet.

Warum die Notwendigkeit einer indirekten Operation: Zwei große Probleme mit dem Gegenmaschinenmodell

Im Folgenden muss man sich daran erinnern, dass diese Modelle abstrakte Modelle sind, die sich von allem physikalisch Realen durch zwei grundlegende Unterschiede unterscheiden: eine unbegrenzte Anzahl von Registern mit jeweils unbegrenzter Kapazität. Das Problem tritt am dramatischsten auf, wenn man versucht, ein Gegenmaschinenmodell zu verwenden, um einen Turing-äquivalenten RASP zu erstellen und damit eine partielle mu-rekursive Funktion zu berechnen :

• Melzak (1961) fügte seinem "Loch-und-Kiesel"-Modell Indirektion hinzu, damit sich sein Modell mit einem "berechneten Goto" selbst modifizieren konnte, und liefert zwei Beispiele für seine Verwendung ("Dezimaldarstellung in der Skala von d" und "Sorting by Magnitude", ob diese in seinem Beweis verwendet werden, dass das Modell Turing-Äquivalent ist, ist unklar, da "das Programm selbst dem Leser als Übung überlassen wird" (S. 292)). Minsky (1961, 1967) konnte zeigen, dass das Registermodell bei geeigneter (aber schwer zu verwendender) Gödel- Zahlencodierung keine Indirektion benötigt, um Turing-äquivalent zu sein; aber es brauchte mindestens ein unbegrenztes Register. Wie unten angemerkt, weist Minsky (1967) auf das Problem eines RASP hin, bietet aber keine Lösung an. Elgot und Robinson (1964) haben bewiesen, dass ihr RASP-Modell P ₀  – es hat keine Indirektionsfähigkeit – nicht alle "rekursiven sequentiellen Funktionen" (mit Parametern beliebiger Länge) berechnen kann, wenn es nicht die Fähigkeit besitzt, seine eigenen Anweisungen zu modifizieren, aber es kann über Gödel-Nummern, wenn dies der Fall ist (S. 395-397; insbesondere Abbildung 2 und Fußnote S. 395). Andererseits kann ihr mit einem "Indexregister" (indirekte Adressierung) ausgestattetes RASP-Modell P' ₀ alle "teilrekursiven sequentiellen Funktionen" (die mu-rekursiven Funktionen) berechnen (S. 397-398).

Cook und Reckhow (1973) sagen es am treffendsten:

Die indirekten Befehle sind notwendig, damit ein festes Programm auf eine unbegrenzte Anzahl von Registern zugreifen kann, wenn sich die Eingänge ändern." (S. 73)

• Unbounded Kapazitäten von Registern im Vergleich begrenzt Kapazitäten der staatlichen Maschinenbefehle : Der so genannte Finite - Zustand Teil der Maschine sein sollten - von der üblichen Definition der Algorithmus - sehr endliche sowohl in der Anzahl der „Zustände“ (Anleitung) und die die Größen der Anweisungen (ihre Kapazität, Symbole/Zeichen zu halten). Wie also verschiebt eine Zustandsmaschine eine beliebig große Konstante direkt in ein Register, zB MOVE (k, r) (Move constant k to register r)? Sind riesige Konstanten notwendig, müssen diese entweder in den Registern selbst beginnen oder von der Zustandsmaschine mit endlich vielen Befehlen erzeugt werden, zB multiplizieren und Subroutinen mit INC und DEC hinzufügen (aber nicht eine quasi-unendliche Zahl davon!).

Manchmal wird die Konstante k durch die Verwendung von CLR ( r ) gefolgt von INC ( r ) erzeugt, die k-mal wiederholt werden – zB um die Konstante k = 3 in das Register r zu setzen, dh 3 → r, also am Ende der Anweisung [r ]=3: CLR (r), INC (r), INC (r), INC (r). Dieser Trick wird von Kleene (1952) p. 223. Das Problem entsteht, wenn die zu erzeugende Zahl die Zahl der Befehle erschöpft, die der endlichen Zustandsmaschine zur Verfügung stehen; es gibt immer eine größere Konstante als die Anzahl der Befehle, die dem endlichen Automaten zur Verfügung stehen.

• Unbegrenzte Anzahl von Registern gegenüber begrenzten Zustandsmaschinenbefehlen : Dies ist schwerwiegender als das erste Problem. Dieses Problem tritt insbesondere auf, wenn wir versuchen, einen sogenannten RASP zu bauen, eine "universelle Maschine" (siehe mehr unter Universal Turing-Maschine ), die ihren endlichen Automaten verwendet, um ein in ihren Registern befindliches "Programm von Befehlen" zu interpretieren – dh wir bauen mit der von-Neumann-Architektur das, was man heute Computer nennt .

Beachten Sie, dass der endliche Automat des Zählers ein Register explizit (direkt) durch seinen Namen/ seine Nummer aufrufen muss : INC (65,356) ruft die Registernummer "65,365" explizit auf . Wenn die Anzahl der Register die Fähigkeit der endlichen Zustandsmaschine überschreitet , sie zu adressieren, dann sind Register außerhalb der Grenzen nicht erreichbar. Wenn beispielsweise die endliche Zustandsmaschine nur 65.536 = 2 ¹⁶ Register erreichen kann, wie kann sie dann die 65.537. erreichen?

Also , wie Sie adressieren wir ein Register über die Grenzen des endlichen Automaten? Ein Ansatz wäre, die Programmanweisungen (die in den Registern gespeicherten) so zu modifizieren , dass sie mehr als einen Befehl enthalten. Aber auch diese kann erschöpft sein, es sei denn, eine Anweisung hat (potenziell) unbegrenzte Größe. Warum also nicht einfach eine "Über-Anweisung" verwenden – eine wirklich sehr große Zahl – die alle darin codierten Programmanweisungen enthält ! So löst Minsky das Problem, aber die von ihm verwendete Gödel-Nummerierung stellt eine große Unannehmlichkeit für das Modell dar, und das Ergebnis entspricht überhaupt nicht unserer intuitiven Vorstellung von einem "gespeicherten Programmcomputer".

Zu einem ähnlichen Ergebnis kommen Elgot und Robinson (1964) hinsichtlich eines "endlich bestimmten" RASP. Es kann zwar auf eine unbegrenzte Anzahl von Registern zugreifen (zB um Befehle daraus abzurufen), aber nur, wenn der RASP eine "Selbstmodifikation" seiner Programmbefehle erlaubt und seine "Daten" in eine Gödel-Zahl kodiert hat (Abb. 2 S. 396 .). ).

Im Kontext eines eher computerähnlichen Modells quält uns Minsky (1967) mit seiner RPT-Anweisung (Repeat) mit einer Lösung des Problems (vgl. S. 214, S. 259), bietet aber keine feste Lösung. Er behauptet:

„Im Allgemeinen kann eine RPT-Operation keine Anweisung im endlichen Teil der Maschine sein … dies könnte jede bestimmte Speichermenge, die im endlichen Teil des Computers zulässig ist, erschöpfen [sic, sein Name für seine RAM-Modelle]. RPT-Operationen erfordern eigene unendliche Register." (S. 214).

Er bietet uns ein beschränktes RPT an, das zusammen mit CLR (r) und INC (r) jede primitive rekursive Funktion berechnen kann , und er bietet das oben zitierte unbeschränkte RPT an, das die Rolle des μ-Operators spielt; es kann zusammen mit CLR (r) und INC (r) die mu-rekursiven Funktionen berechnen. Aber er spricht nicht von "Indirektion" oder dem RAM-Modell an sich.

Aus den Referenzen in Hartmanis (1971) geht hervor, dass Cook (in seinen Vorlesungsnotizen an der UC Berkeley, 1970) den Begriff der indirekten Adressierung verfestigt hat. Deutlicher wird dies in der Arbeit von Cook und Reckhow (1973) – Cook ist Reckhows Betreuer für die Masterarbeit. Das Modell von Hartmanis – ziemlich ähnlich dem Modell von Melzak (1961) – verwendet Additionen und Subtraktionen mit zwei und drei Registern und zwei Parameterkopien; Das Modell von Cook und Reckhow reduziert die Anzahl der Parameter (in den Programmanweisungen aufgerufene Register) auf einen Aufruf durch Verwendung eines Akkumulators "AC".

Die Lösung in Kürze: Entwerfen Sie unsere Maschine/unser Modell mit unbegrenzter Indirektion  – stellen Sie ein unbegrenztes "Adressregister" bereit , das potenziell jedes beliebige Register benennen (aufrufen) kann, egal wie viele es sind. Damit dies funktioniert, muss das unbegrenzte Register im Allgemeinen gelöscht und dann durch eine potenziell unendliche Schleife inkrementiert (und möglicherweise dekrementiert) werden. In diesem Sinne stellt die Lösung den unbegrenzten μ-Operator dar , der bei Bedarf die unbegrenzte Reihe von Registern bis ins Unendliche durchsuchen kann, bis er findet, wonach er sucht. Das Zeigerregister ist genau wie jedes andere Register mit einer Ausnahme: Unter Umständen, die als "indirekte Adressierung" bezeichnet werden, liefert es seinen Inhalt und nicht den Adressoperanden in der TABLE der Zustandsmaschine als Adresse des Zielregisters (einschließlich möglicherweise sich selbst). !).

Begrenzte Indirektion und die primitiven rekursiven Funktionen

Wenn wir den Minsky-Ansatz einer Monsterzahl in einem Register vermeiden und angeben, dass unser Maschinenmodell "wie ein Computer" sein wird, müssen wir uns diesem Problem der Indirektion stellen, wenn wir die rekursiven Funktionen (auch μ-rekursiv genannt) berechnen wollen Funktionen ) – sowohl totale als auch partielle Varietäten.

Unser einfacheres Gegenmaschinenmodell kann eine „begrenzte“ Form der Indirektion durchführen – und dadurch die Unterklasse primitiver rekursiver Funktionen berechnen  – indem es einen primitiven rekursiven „Operator“ namens „Definition durch Fälle“ verwendet (definiert in Kleene (1952) p 229 und Boolos-Burgess-Jeffrey S. 74). Eine solche "begrenzte Umleitung" ist eine mühsame, langwierige Angelegenheit. "Definition durch Fälle" erfordert, dass die Maschine den Inhalt des Zeigerregisters bestimmt/unterscheidet, indem sie bis zum Erfolg immer wieder versucht, diesen Inhalt mit einer Zahl/einem Namen abzugleichen, die der Falloperator explizit deklariert. So beginnt die Definition nach Fällen z. B. bei der unteren Grenzadresse und geht bis zum Überdruss in Richtung der oberen Grenzadresse weiter, um eine Übereinstimmung zu erzielen:

Ist die Zahl im Register N gleich 0? Wenn nicht, ist es dann gleich 1? 2? 3? ... 65364? Wenn nicht, dann sind wir bei der letzten Nummer 65365 und diese sollte besser diejenige sein, sonst haben wir ein Problem!

Die "begrenzte" Indirektion erlaubt uns nicht, die partiellen rekursiven Funktionen zu berechnen – für diese brauchen wir die unbeschränkte Indirektion, auch bekannt als μ-Operator .

Angenommen, wir hätten bis zur Nummer 65367 weiterfahren können, und tatsächlich enthielt dieses Register, was wir suchten. Dann hätten wir unsere Berechnung erfolgreich abschließen können! Aber nehmen wir an, 65367 hätte nicht das, was wir brauchten. Wie weit sollen wir noch gehen?

Um Turing-Äquivalent zu sein, muss die Zählermaschine entweder die unglückliche Minsky- Gödel- Zahlenmethode mit einem einzigen Register verwenden oder um die Fähigkeit erweitert werden, die Enden ihrer Registerkette, falls erforderlich, bis ins Unendliche zu erkunden. (Das Versäumnis, etwas "da draußen" zu finden, definiert, was es bedeutet, wenn ein Algorithmus nicht terminiert; vgl. Kleene (1952) S. 316ff Kapitel XII Partial Recursive Functions , insbesondere S. 323-325.) Siehe mehr dazu in das Beispiel unten.

Unbeschränkte Indirektion und die partiellen rekursiven Funktionen

Für eine unbegrenzte Indirektion benötigen wir eine "Hardware"-Änderung in unserem Maschinenmodell. Sobald wir diese Änderung vornehmen, ist das Modell keine Gegenmaschine mehr, sondern eine Maschine mit wahlfreiem Zugriff.

Wenn nun zB INC angegeben wird, muss der Befehl des endlichen Automaten angeben, woher die Adresse des interessierenden Registers kommt. Diese wo entweder (i) die Anweisung des Zustandsmaschine , die eine bietet explizite Bezeichnung , oder (ii) die Zeiger-Register , dessen Inhalt ist die Adresse von Interesse. Immer wenn eine Anweisung eine Registeradresse angibt, muss sie jetzt auch einen zusätzlichen Parameter "i/d" – "indirekt/direkt" angeben. In gewisser Weise ist dieser neue "i/d"-Parameter ein "Schalter", der umlegt, um die direkte Adresse wie in der Anweisung angegeben zu erhalten, oder um die indirekte Adresse aus dem Zeigerregister (welches Zeigerregister – in einigen modelliert jedes Register kann ein Zeigerregister sein – wird durch die Anweisung spezifiziert). Diese "sich gegenseitig ausschließende, aber erschöpfende Wahl" ist ein weiteres Beispiel für "Definition durch Fälle", und das im folgenden Beispiel gezeigte arithmetische Äquivalent stammt aus der Definition in Kleene (1952) S. 229.

Beispiel: CPY ( indirekte _Quelle , r _Quelle , direktes _Ziel , r _Ziel )

Weisen Sie einen Code zu, um die direkte Adressierung als d="0" und die indirekte Adressierung als i="1" anzugeben. Dann kann unsere Maschine die Quelladresse wie folgt ermitteln:

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

Angenommen, der Inhalt von Register 3 ist "5" (dh [3]=5 ) und der Inhalt von Register 4 ist "2" (dh [4]=2 ):

Beispiel: CPY ( 1, 3, 0, 4 ) = CPY ( indirekt, reg 3, direkt, reg 4 )

1*[3] + 0*3 = [3] = Quellregisteradresse 5

0*[4] + 1*4 = 4 = Zielregisteradresse 4

Beispiel: KPY ( 0, 3, 0, 4 )

0*[3] + 1*3 = 3 = Quellregisteradresse 3

0*[4] + 1*4 = 4 = Zielregisteradresse 4

Beispiel: KPY ( 0, 3, 1, 4 )

0*[3] + 1*3 = 3 = Quellregisteradresse 3

1*[4] + 0*4 = [4] = Zielregisteradresse 2

Die indirekte COPY-Anweisung

Die wahrscheinlich nützlichste der hinzugefügten Anweisungen ist COPY. Tatsächlich liefern Elgot-Robinson (1964) ihre Modelle P ₀ und P' ₀ mit den COPY-Anweisungen, und Cook-Reckhow (1973) liefert ihr akkumulatorbasiertes Modell nur mit zwei indirekten Anweisungen – COPY zum Akkumulator indirekt, COPY vom Akkumulator indirekt .

Eine Fülle von Befehlen : Da jeder Befehl, der auf ein einzelnes Register wirkt, mit seinem indirekten "Dual" erweitert werden kann (einschließlich bedingter und unbedingter Sprünge, siehe das Elgot-Robinson-Modell), verdoppelt die Einbeziehung indirekter Befehle die Anzahl der einzelnen Parameter/ Registerbefehle (zB INC (d, r), INC (i, r)). Schlimmer noch, jeder zwei Parameter-/Registerbefehl hat 4 mögliche Varianten, zB:

CPY (d, r _s , d, r _d ) = COPY direkt vom Quellregister direkt in das Zielregister

CPY (i, r _sp , d, r _d ) = COPY in das Zielregister indirekt unter Verwendung der Quelladresse, die im Quellzeigerregister r _{sp zu finden ist} .

CPY (d, r _s , i, r _dp ) = COPY Inhalt des Quellenregister indirekt in das Register unter Verwendung Zieladresse in dem Ziel-Zeigerregister r gefunden werden _dp .

CPY (i, r _sp , i, r _dp ) = KOPIEREN indirekt den Inhalt des Quellregisters mit Adresse im Quellzeigerregister r _sp , in das Zielregister mit Adresse im Zielzeigerregister r _dp )

In ähnlicher Weise führt jeder Drei-Register-Befehl, der zwei Quellregister r _s1 r _s2 und ein Zielregister r _{d umfasst} , zu 8 Varianten, zum Beispiel die Addition:

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

wird ergeben:

• HINZUFÜGEN ( d, _rs1 , d, _rs2 , d, r _d )
• _HINZUFÜGEN (i, r _sp1 , d, _rs2 , d, r _d )
• HINZUFÜGEN ( d, r _s1 , i, r _sp2 , d, r _d )
• _HINZUFÜGEN ( i, r _sp1 , i, r _sp2 , d, r _d )
• HINZUFÜGEN ( d, r _s1 , d, r _s2 , i, r _dp )
• _HINZUFÜGEN ( i, r _sp1 , d, r _s2 , i, r _dp )
• HINZUFÜGEN ( d, r _s1 , i, r _sp2 , i, r _dp )
• _HINZUFÜGEN ( i, r _sp1 , i, r _sp2 , i, r _dp )

Wenn wir ein Register als "Akkumulator" bezeichnen (siehe unten) und die verschiedenen zulässigen Anweisungen stark einschränken, können wir die Fülle der direkten und indirekten Operationen stark reduzieren. Man muss jedoch sicher sein, dass der resultierende reduzierte Befehlssatz ausreichend ist, und wir müssen uns bewusst sein, dass die Reduzierung auf Kosten von mehr Befehlen pro "signifikanter" Operation geht.

Der Begriff "Akkumulator A"

Die historische Konvention widmet dem Akkumulator ein Register, einem "Rechenorgan", das seine Zahl während einer Folge von Rechenoperationen buchstäblich akkumuliert:

"Der erste Teil unseres Rechenorgans ... sollte ein paralleles Speicherorgan sein, das eine Zahl aufnehmen und zu der bereits vorhandenen hinzufügen kann, die auch ihren Inhalt löschen und speichern kann, was sie enthält. Wir werden eine solche Orgel einen Akkumulator nennen . Es ist im Prinzip ganz gebräuchlich in früheren und heutigen Rechenmaschinen verschiedenster Art, zB Tischmultiplikatoren, Standard-IBM-Zähler, modernere Relaismaschinen, die ENIAC" (fettgedruckt im Original: Goldstine und von Neumann , 1946, S. 98 in Bell und Newell 1971).

Der Akkumulator geht jedoch auf Kosten von mehr Befehlen pro arithmetischer "Operation", insbesondere in Bezug auf sogenannte "Lesen-Modifizieren-Schreiben"-Befehle wie "Inkrementiere indirekt den Inhalt des Registers, auf das Register r2 zeigt". "A" bezeichnet das "Akkumulator"-Register A:

Etikett	Anweisung		EIN	r2	r378.426	Beschreibung
			. . .	378.426	17
INCI ( r2 ):	KPY ( i, r2, d, A )		17	378.426	17	Inhalt von r2 zeigt auf r378.426 mit Inhalt "17": kopiere dies nach A
	INC (A)		18	378.426	17	Inzementgehalt von A
	KPY ( d, A, i, r2 )		18	378.426	18	Inhalt von r2 zeigt auf r378,426: Inhalt von A in r378,426 kopieren

Bleiben wir bei einem bestimmten Namen für den Akkumulator, zB "A", können wir den Akkumulator in der Anleitung zum Beispiel implizieren,

INC ( A ) = INCA

Wenn wir jedoch die CPY-Anweisungen ohne den aufgerufenen Akkumulator schreiben, sind die Anweisungen mehrdeutig oder müssen leere Parameter haben:

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

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

Historisch gesehen haben diese beiden CPY-Anweisungen unterschiedliche Namen erhalten; es gibt jedoch keine Konvention. Tradition (zB Knuths (1973) imaginärer MIX- Computer) verwendet zwei Namen, die LOAD und STORE genannt werden. Hier fügen wir den Parameter "i/d" hinzu:

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 )

Das typische akkumulatorbasierte Modell hat alle seine zweivariablen arithmetischen und konstanten Operationen (z. B. ADD (A, r), SUB (A, r) ) verwenden (i) den Inhalt des Akkumulators zusammen mit (ii) dem Inhalt eines spezifizierten Registers . Die Operationen mit einer Variablen (zB INC (A), DEC (A) und CLR (A) ) erfordern nur den Akkumulator. Beide Befehlsarten legen das Ergebnis (zB Summe, Differenz, Produkt, Quotient oder Rest) im Akkumulator ab.

Beispiel: INCA = [A] +1 → A

Beispiel: ADDA (r _s ) = [A] + [r _s ] → A

Beispiel: MULA (r _s ) = [A] * [r _s ] → A

Wenn wir dies wünschen, können wir die Mnemonik abkürzen, da mindestens ein Quellregister und das Zielregister immer der Akkumulator A ist. Somit haben wir:

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

Der Begriff des indirekten Adressregisters "N"

Wenn unser Modell einen unbegrenzten Akkumulator hat, können wir dann alle anderen Register begrenzen ? Erst wenn wir für mindestens ein unbegrenztes Register sorgen, aus dem wir unsere indirekten Adressen ableiten.

Der minimalistische Ansatz besteht darin, sich selbst zu nutzen (Schönhage macht das).

Ein anderer Ansatz (Schönhage macht dies auch) besteht darin, ein bestimmtes Register zum "indirekten Adressregister" zu deklarieren und die Indirektion relativ zu diesem Register zu beschränken (Schonhages RAM0-Modell verwendet sowohl A- als auch N-Register für indirekte sowie direkte Befehle). Auch hier hat unser neues Register keinen herkömmlichen Namen – vielleicht "N" von "iNdex", oder "iNdirect" oder "Adressnummer".

Für maximale Flexibilität, wie wir es für den Akkumulator A getan haben, betrachten wir N als ein weiteres Register, das dem Inkrementieren, Dekrementieren, Löschen, Testen, Direktkopieren usw. unterliegt und indirekt, zum Beispiel.

LDAN (i/d) = CPY (i/d, N, d, A); Laden Sie den Akkumulator über das iNdirection-Register

STAN (i/d) = CPY (d, A, i/d, N). STore Akkumulator über das iNdirection-Register

Warum ist das ein so interessanter Ansatz? Mindestens zwei Gründe:

(1) Ein Befehlssatz ohne Parameter:

Schönhage macht dies, um seinen RAM0-Befehlssatz zu erzeugen. Siehe Abschnitt unten.

(2) Reduzieren Sie einen RAM auf eine Post-Turing-Maschine:

Indem wir uns als Minimalisten ausgeben, reduzieren wir alle Register mit Ausnahme des Akkumulators A und des Indirektionsregisters N, zB r = { r0, r1, r2, ... } auf eine unbegrenzte Folge von (sehr) beschränkten Schubladen. Diese werden nichts anderes tun, als (sehr) begrenzte Zahlen zu halten, zB ein einzelnes Bit mit dem Wert { 0, 1 }. Ebenso verkleinern wir den Akkumulator auf ein einzelnes Bit. Wir beschränken jede Arithmetik auf die Register { A, N }, verwenden indirekte Operationen, um den Inhalt von Registern in den Akkumulator zu ziehen und schreiben 0 oder 1 aus dem Akkumulator in ein Register:

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

Wir drängen weiter und eliminieren A durch die Verwendung von zwei "konstanten" Registern namens "ERASE" und "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 ( ich _z ), H }

Benennen Sie die COPY-Anweisungen um und rufen Sie INC (N) = RIGHT, DEC (N) = LEFT auf und wir haben die gleichen Anweisungen wie die Post-Turing-Maschine, plus eine zusätzliche CLRN:

{ LÖSCHEN, DRUCKEN, CLRN, RECHTS, LINKS, JZ (i, N, I _z ), JZ (I _z ), H }

Turing-Äquivalenz des RAM mit Indirektion

Im obigen Abschnitt haben wir informell gezeigt, dass ein RAM mit unbegrenzter Indirektionsfähigkeit eine Post-Turing-Maschine erzeugt . Die Post-Turing-Maschine ist Turing-Äquivalent, also haben wir gezeigt, dass der RAM mit Indirektion Turing-Äquivalent ist.

Wir geben hier eine etwas formellere Demonstration. Beginnen Sie mit dem Entwerfen unseres Modells mit drei reservierten Registern "E", "P" und "N" plus einem unbegrenzten Satz von Registern 1, 2, ..., n rechts. Die Register 1, 2, ..., n werden als "die Quadrate des Bandes" betrachtet. Register "N" zeigt auf "das gescannte Quadrat", das "der Kopf" gerade beobachtet. Man kann sich den "Kopf" im bedingten Sprung vorstellen – man beachte, dass er indirekte Adressierung verwendet (vgl. Elgot-Robinson S. 398). Wenn wir "N" dekrementieren oder inkrementieren, bewegt sich der (scheinbare) Kopf entlang der Quadrate "nach links" oder "rechts". Wir verschieben den Inhalt von "E"=0 oder "P"=1 auf das "gescannte Quadrat", auf das N zeigt, unter Verwendung des indirekten CPY.

Die Tatsache, dass unser Band linksseitig ist, stellt uns vor ein kleines Problem: Immer wenn LEFT auftritt, müssen unsere Anweisungen testen, ob der Inhalt von "N" Null ist oder nicht; wenn ja, sollten wir die Zählung bei "0" belassen (dies ist unsere Wahl als Designer – zum Beispiel könnten wir die Maschine/das Modell "ein Ereignis auslösen" unserer Wahl haben).

Befehlssatz 1 (erweitert): { INC (N), DEC (N), CLR (N), CPY (d, r _s ,i, N), JZ ( i, r, z ), HALT }

Die folgende Tabelle definiert sowohl die Post-Turing-Befehle hinsichtlich ihrer RAM-äquivalenten Befehle als auch ein Beispiel ihrer Funktionsweise. Die (scheinbare) Position des Kopfes entlang des Bandes der Register r0-r5 . . . ist schattiert dargestellt:

Gedächtnisstütze	Etikett:			E	P	n		r0	r1	r2	r3	r4	r5	usw.	Aktion bei Registern	Aktion am endlichen Automaten Befehlsregister IR
	Anfang:			0	1	3					1	0
R	rechts:	INC ( N )		0	1	4					1	0			[N] +1 → N	[IR] +1 → IR
P	drucken:	KPY ( d, P, i, N )		0	1	4					1	1			[P]=1 → [N]=r4	[IR] +1 → IR
E	löschen:	KPY ( d, E, i, N )		0	1	4					1	0			[E]=0 → [N]=r4	[IR] +1 → IR
L	links:	JZ ( ich, N, Ende )		0	1	4					1	0			keiner	WENN N =r4] =0 DANN "Ende" → IR sonst [IR]+1 → IR
		DEZ ( N )		0	1	3					1	0			[N] -1 → N
J0 ( halt )	jump_if_blank:	JZ ( ich, N, Ende )		0	1	3					1	0			keiner	WENN N =r3] =0 DANN "Ende" → IR sonst [IR]+1 → IR
J1 ( halt )	jump_if_mark:	JZ ( ich, N, halt )		0	1	3					1	0			N =r3] → A	WENN N =r3] =0 DANN "Ende" → IR sonst [IR]+1 → IR
	Ende	. . . usw.		0	1	3					1	0
	Halt:	h		0	1	3					1	0			keiner	[IR] +1 → IR

Beispiel: Begrenzte Indirektion ergibt eine Maschine, die nicht Turing-äquivalent ist

Während dieser Demonstration müssen wir bedenken, dass die Anweisungen in der TABLE des endlichen Automaten beschränkt sind , dh endlich :

"Neben der Tatsache, dass ein Algorithmus lediglich ein endlicher Satz von Regeln ist, der eine Folge von Operationen zur Lösung eines bestimmten Problemtyps vorgibt, hat ein Algorithmus fünf wichtige Merkmale [Endlichkeit, Bestimmtheit, Eingabe, Ausgabe, Wirksamkeit]" (kursiv hinzugefügt, Knuth S. 4 -7).

Die Schwierigkeit entsteht, weil die Register eindeutige "Namen" (Nummern) haben und unsere Maschine jedes mit Namen aufrufen muss, um darauf "zuzugreifen".

Wir bauen die indirekte CPY ( i, q, d, φ ) mit dem CASE-Operator. Die Adresse des Zielregisters wird durch den Inhalt des Registers "q" spezifiziert; Sobald der CASE-Operator diese Nummer bestimmt hat, wird CPY den Inhalt des Registers mit dieser Nummer direkt im Register "φ" ablegen. Wir benötigen ein zusätzliches Register, das wir „y“ nennen – es dient als Aufwärtszähler.

Das Folgende ist also tatsächlich eine konstruktive Demonstration oder ein Beweis dafür, dass wir tatsächlich die indirekte CPY ( i, q, d, φ ) simulieren können, ohne eine "Hardware" -Designänderung an unserer Gegenmaschine / unserem Gegenmodell vorzunehmen. Beachten Sie jedoch, dass ein RASP, der diese indirekte CPY verwendet, nur die primitiven rekursiven Funktionen berechnen kann , nicht die vollständige Suite von mu-rekursiven Funktionen , da diese indirekte CPY durch die Größe/Ausdehnung der endlichen Zustandsmaschine "begrenzt" ist .

Der CASE "Operator" wird in Kleene (1952) (S. 229) und in Boolos-Burgess-Jeffrey (2002) (S. 74) beschrieben; letztere Autoren betonen seine Nützlichkeit. Die folgende Definition ist nach Kleene, aber modifiziert, um die bekannte "IF-THEN-ELSE"-Konstruktion widerzuspiegeln.

Der CASE-Operator "gibt" eine natürliche Zahl in φ zurück, je nachdem welcher "Fall" erfüllt ist, beginnend mit "case_0" und nacheinander bis "case_last"; wenn kein Fall erfüllt ist, wird die Zahl namens "default" (auch bekannt als "woops") in φ zurückgegeben (hier bezeichnet x eine Auswahl von Parametern, z. B. Register q und die Zeichenfolge r0, ... rlast )):

Definition nach Fällen φ ( x , y):

• case_0: WENN Q ₀ ( x , y) wahr ist DANN φ ₀ ( x , y) ELSE
• case_1: WENN Q ₁ ( x , y) wahr ist DANN φ ₁ ( x , y) ELSE
• Fälle_2 bis Fall_next_to_last: usw. . . . . . . . . ANDERS
• case_last: WENN Q _last ( x , y) wahr ist DANN φ _last ( x , y) ELSE
• Vorgabe: tun φ _Vorgabe ( x , y)

Kleene verlangt, dass sich die "Prädikate" Q _n gegenseitig ausschließen – "Prädikate" sind Funktionen, die nur { true, false } für die Ausgabe erzeugen; Boolos-Burgess-Jeffrey fügt hinzu, dass die Fälle "erschöpfend" sind.

Wir beginnen mit einer Zahl im Register q, die die Adresse des Zielregisters darstellt. Aber was ist diese Zahl? Die "Prädikate" testen es, um einen Versuch nach dem anderen herauszufinden: JE (q, y, z) gefolgt von INC (y). Sobald die Nummer explizit identifiziert wurde, kopiert der CASE-Operator den Inhalt dieses Registers direkt/explizit nach φ:

Fallunterscheidung CPY (i, q, d, φ) = _def φ (q, r 0, ..., rlast, y) =

• case_0: WENN CLR (y), [q] - [y]=0 DANN CPY ( r0, φ ), J (Ausgang) ELSE
• case_1: WENN INC (y), [q] = [y]=1 THEN CPY ( r1, φ ), J (Ausgang) ELSE
• case_2 bis case n: IF . . . DANN . . . ANDERS
• case_n: WENN INC (y), [q] = [y]=n DANN CPY ( rn, φ ), J (Ausgang) ELSE
• case_n+1 bis case_last: IF . . . DANN . . . ANDERS
• case_last: IF INC (y), [q] = [y]="last" THEN CPY ( rlast, φ ), J (exit) ELSE
• Standard: Woops

Case_0 (der Basisschritt der Rekursion auf y) sieht so aus:

• fall_0 :

• CLR (j); setze Register y = 0
• JE ( q, y, _φ0 )
• J ( Fall_1 )

• _φ0: CPY ( r0, φ )
• J ( Ausgang )

• Fall_1: usw.

Case_n (der Induktionsschritt) sieht so aus; Denken Sie daran, dass jede Instanz von "n", "n+1", ..., "last" eine explizite natürliche Zahl sein muss:

• fall_n :

• INC ( J )
• JE ( q, y, _φn )
• J ( fall_n+1 )

• _φn: CPY ( rn, φ )
• J ( Ausgang )

• Fall__n+1: usw.

Case_last stoppt die Induktion und begrenzt den CASE-Operator (und damit den "indirect copy"-Operator):

• fall_letzter :

• INC ( J )
• JE ( q, y, _φletzter )
• J ( wup )

• _φlast : CPY ( rlast, φ )
• J ( Ausgang )

• woops: Wie gehen wir mit einem Out-of-Bounds-Versuch um?
• Ausgang: usw.

Wenn der CASE bis ins Unendliche fortgesetzt werden könnte, wäre es der mu-Operator . Aber es kann nicht – das "Zustandsregister" seiner endlichen Zustandsmaschine hat seinen maximalen Zählwert erreicht (zB 65365 = 11111111,11111111 ₂ ) oder seine Tabelle hat keine Befehle mehr; es ist schließlich eine endliche Maschine.

Beispiele für Modelle

Register-zu-Register-Modell ("read-modify-write") von Cook und Reckhow (1973)

Das häufig anzutreffende Cook- und Rechkow-Modell ähnelt dem ternären Malzek-Modell (mit Knuth-Mnemonik geschrieben – die Originalanleitung hatte keine Mnemonik außer TRA, Read, Print).

• LOAD ( C, rd ) ; C → rd, C ist eine ganze Zahl

Beispiel: LOAD ( 0, 5 )löscht Register 5.

• ADD ( rs1, rs2, rd ) ; [rs1] + [rs2] → rd, die Register können gleich oder verschieden sein;

Beispiel: ADD ( A, A, A )verdoppelt den Inhalt von Register A.

• SUB ( rs1, rs2, rd ) ; [rs1] - [rs2] → rd, die Register können gleich oder unterschiedlich sein:

Beispiel: SUB ( 3, 3, 3 )löscht Register 3.

• COPY ( i, rp, d, rd ) ; [[rp] ] → rd, Kopieren Sie indirekt den Inhalt des Quellregisters, auf das das Zeigerregister r _{p zeigt,} in das Zielregister.
• COPY ( d, rs, i, rp ) ; [rs] → [rp]. Kopieren Sie den Inhalt des Quellregisters r _s in das Zielregister, auf das das Zeigerregister r _{p zeigt} .
• JNZ ( r, Iz ) ;Bedingter Sprung, wenn [r] positiv ist; dh IF [r] > 0 THEN springe zu Anweisung z sonst weiter der Reihe nach (Cook und Reckhow nennen das: "Transfer control to line m if Xj > 0")
• READ ( rd ) ;kopiere "die Eingabe" in das Zielregister r _d
• PRINT ( rs ) ;Kopieren Sie den Inhalt des Quellregisters r _s in "die Ausgabe".

Schönhages RAM0 und RAM1 (1980)

Schönhage (1980) beschreibt ein sehr primitives, atomisiertes Modell, das für seinen Beweis der Äquivalenz seines SMM- Zeigermaschinenmodells ausgewählt wurde :

"Um eine explizite Adressierung zu vermeiden, verfügt das RAM0 über den Akkumulator mit Inhalt z und ein zusätzliches Adressregister mit aktuellem Inhalt n (zunächst 0)" (S. 494)

RAM1-Modell : Schönhage demonstriert, wie seine Konstruktion verwendet werden kann, um die üblichere, verwendbarere Form von "Nachfolger"-ähnlichem RAM zu bilden (unter Verwendung der Mnemonik dieses Artikels):

• LDA k ; k --> A , k ist eine Konstante, eine explizite Zahl wie "47"
• LDA ( d, r ) ; [r] → A ; A direkt laden
• LDA ( i, r ) ; [[r]] → A ; indirekt laden A
• STA ( d, r ) ; [A] → r ; A direkt speichern
• STA ( i, r ) ; [A] → [r] ; indirekt speichern A
• JEA ( r, z ) ; IF [A] = [r] then Iz else continue
• INCA ; [A] + 1 --> A

RAM0-Modell : Schönhages RAM0-Maschine hat 6 Anweisungen, die durch einen einzelnen Buchstaben gekennzeichnet sind (das 6. "C xxx" scheint das "Überspringen des nächsten Parameters" zu beinhalten. Schönhage bezeichnet den Akkumulator mit "z", "N" mit "n" usw. Anstelle von Schönhages Mnemonik werden wir die oben entwickelten Mnemoniken verwenden.

• (Z), CLRA: 0 → A
• (A), INCA: [A] +1 → A
• (N), CPYAN: [A] → N
• (A), LDAA: [[A]] → A ; Inhalt von A zeigt auf Registeradresse; setze den Inhalt des Registers in A
• (S), STAN: [A] → [N] ; Inhalt von N Punkten zur Registeradresse; setze den Inhalt von A in ein Register, auf das N . zeigt
• (C), JAZ ( z ): [A] = 0 then go to Iz ; zweideutig in seiner Behandlung

Die Indirektion kommt (i) von CPYAN (Inhalte A nach N kopieren/übertragen), die mit store_A_via_N STAN arbeitet, und von (ii) der eigentümlichen Indirektionsanweisung LDAA ( [[A]] → [A] ).

Fußnoten

Endlich vs unbegrenzt

Die definitionsgemäße Tatsache, dass jede Art von Zählermaschine ohne ein unbegrenztes Register-"Adress"-Register ein Register "r" mit Namen spezifizieren muss, zeigt an, dass das Modell erfordert, dass "r" endlich ist , obwohl es "unbegrenzt" in dem Sinne ist, dass die Das Modell impliziert keine Obergrenze für die Anzahl der Register, die für seine Aufgabe(n) erforderlich sind. Zum Beispiel benötigen wir weder r < 83.617.563.821.029.283.746 noch r < 2^1.000.000 usw.

Somit kann unser Modell die Anzahl der Register "erweitern", falls dies erforderlich ist, um eine bestimmte Berechnung durchzuführen. Dies bedeutet jedoch , dass jede Zahl, auf die das Modell erweitert wird, endlich  sein muss – sie muss mit einer natürlichen Zahl indiziert werden: ω ist keine Option .

Wir können diese Einschränkung umgehen, indem wir ein unbegrenztes Register bereitstellen, um die Adresse des Registers bereitzustellen, das eine indirekte Adresse angibt.

Siehe auch

• Echter RAM
• Transdichotomes Modell

Externe Links

• Computeremulator mit wahlfreiem Zugriff
• Computeremulator mit wahlfreiem Zugriff
• Computeremulator mit wahlfreiem Zugriff

Verweise

Bis auf wenige Ausnahmen sind diese Referenzen die gleichen wie bei Registermaschine .

• • Goldstine, Herman H. und von Neumann, John, "Planning and Coding of the Problems for an Electronic Computing Instrument", Rep. 1947, Institute for Advanced Study , Princeton. Nachdruck auf S. 92–119 in Bell, C. Gordon und Newell, Allen (1971), Computer Structures: Readings and Example , McGraw-Hill Book Company, New York. ISBN  0-07-004357-4 }.
• George Boolos , John P. Burgess , Richard Jeffrey (2002), Berechenbarkeit und Logik: Vierte Auflage , Cambridge University Press, Cambridge, England. Der ursprüngliche Boolos-Jeffrey-Text wurde von Burgess umfassend überarbeitet: fortgeschrittener als ein einführendes Lehrbuch. Das Modell "Abacus-Maschine" wird ausführlich in Kapitel 5 Abacus Computability entwickelt ; es ist eines von drei ausführlich behandelten und verglichenen Modellen – die Turing-Maschine (immer noch in Boolos' ursprünglicher 4-Tupel-Form) und die Rekursion die anderen beiden.
• Arthur Burks , Herman Goldstine , John von Neumann (1946), Vorläufige Diskussion des logischen Entwurfs eines elektronischen Recheninstruments , Nachdruck S. 92ff in Gordon Bell und Allen Newell (1971), Computer Structures: Readings and Example , mcGraw-Hill Book Unternehmen, New York. ISBN  0-07-004357-4 .
• Stephen A. Cook und Robert A. Reckhow (1973), Time-bounded Random Access Machines , Journal of Computer Systems Science 7(4):354-375.
• Martin Davis (1958), Berechenbarkeit und Unlösbarkeit , McGraw-Hill Book Company, Inc. New York.
• Calvin Elgot und Abraham Robinson (1964), Random-Access Stored-Program Machines, an Approach to Programming Languages , Journal of the Association for Computing Machinery, Bd. 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). Einführung in die Automatentheorie, Sprachen und Berechnung , 1. Aufl., Reading Mass: Addison-Wesley. ISBN  0-201-02988-X . Ein schwieriges Buch, das sich um die Fragen der maschinellen Interpretation von "Sprachen", NP-Vollständigkeit usw.
• Stephen Kleene (1952), Einführung in die Metamathematik , North-Holland Publishing Company, Amsterdam, Niederlande. ISBN  0-7204-2103-9 .
• Donald Knuth (1968), The Art of Computer Programming , Zweite Auflage 1973, Addison-Wesley, Reading, Massachusetts. Vgl. Seiten 462-463, wo er "eine neue Art von abstrakter Maschine oder 'Automaten' definiert, die sich mit verbundenen Strukturen befasst".
• Joachim Lambek (1961, erhalten am 15. Juni 1961), How to Program an Infinite Abacus , Mathematical Bulletin, vol. 4, nein. 3. September 1961, Seiten 295-302. In seinem Anhang II schlägt Lambek eine "formale Definition von 'Programm' vor. Er verweist auf Melzak (1961) und Kleene (1952) Einführung in die Metamathematik .
• ZA Melzak (1961, erhalten am 15. Mai 1961), Ein informeller arithmetischer Ansatz zur Berechenbarkeit und Berechnung , Canadian Mathematical Bulletin , vol. 4, nein. 3. September 1961, Seiten 279-293. Melzak bietet keine Referenzen an, erkennt jedoch "den Nutzen von Gesprächen mit Drs. R. Hamming, D. McIlroy und V. Vyssots von den Bell Telephone Laborators und mit Dr. H. Wang von der Oxford University an."
• Marvin Minsky (1961). „Rekursive Unlösbarkeit des Post-Problems des ‚Tag‘ und anderer Themen in der Theorie der Turingmaschinen“. Annalen der Mathematik . Die Annalen der Mathematik, Bd. 74, Nr. 3. 74 (3): 437–455. doi : 10.2307/1970290 . JSTOR  1970290 .
• Marvin Minsky (1967). Berechnung: Endliche und unendliche Maschinen (1. Aufl.). Englewood Cliffs, NJ: Prentice-Hall, Inc.Siehe insbesondere Kapitel 11: Digitalcomputerähnliche Modelle und Kapitel 14: Sehr einfache Grundlagen der Berechenbarkeit . Im vorherigen Kapitel definiert er "Programmmaschinen" und im späteren Kapitel diskutiert er "Universelle Programmmaschinen mit zwei Registern" und "...mit einem Register" usw.
• John C. Shepherdson und HE Sturgis (1961) erhielten im Dezember 1961 Computability of Recursive Functions , Journal of the Association of Computing Machinery (JACM) 10:217-255, 1963. Ein äußerst wertvolles Referenzpapier. In ihrem Anhang A zitieren die Autoren 4 weitere mit Verweis auf "Minimalität der in 4.1 verwendeten Anweisungen: Vergleich mit ähnlichen Systemen".

• Kaphengst, Heinz, Eine Abstrakte programmgesteuerte Rechenmaschine' , Zeitschrift für mathematische Logik und Grundlagen der Mathematik: 5 (1959), 366-379.
• Ershov, AP Über Operatoralgorithmen , (Russisch) Dok. Akad. Nauk 122 (1958), 967-970. Englische Übersetzung, 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. Semesterberichte (Göttingen) 4 (1954), 42-53.

• Arnold Schönhage (1980), Speichermodifikationsmaschinen , Gesellschaft für industrielle und angewandte Mathematik, SIAM J. Comput. vol. 9, Nr. 3, August 1980. Wobei Schönhage die Äquivalenz seines SMM mit dem "Nachfolger RAM" (Random Access Machine) etc. bzw. Storage Modification Machines , in Theoretical Computer Science (1979), S. 36–37
• Peter van Emde Boas , "Machine Models and Simulations" S. 3–66, in: Jan van Leeuwen , hrsg. Handbuch der Theoretischen Informatik. Band A: Algorithmen und Komplexität , The MIT PRESS/Elsevier, 1990. ISBN  0-444-88071-2 (Band A). QA 76.H279 1990. van Emde Boas' Behandlung von SMMs erscheint auf S. 32–35. Diese Behandlung verdeutlicht Schönhage 1980 – sie schließt sich eng an die Schönhage-Behandlung an, erweitert sie jedoch geringfügig. Beide Referenzen können für ein effektives Verständnis erforderlich sein.
• Hao Wang (1957), A Variant to Turing's Theory of Computing Machines , JACM (Journal of the Association for Computing Machinery) 4; 63-92. Präsentiert auf der Vereinsversammlung vom 23.-25. Juni 1954.