Zufallszugriffsmaschine

Im Informatik, Zufallszugriffsmaschine (RAM) ist ein abstrakte Maschine in der allgemeinen Klasse von Maschinen registrieren. Der RAM ist dem sehr ähnlich wie der Zählermaschine aber mit der zusätzlichen Fähigkeit der "indirekten Adressierung" seiner Register. Wie die Zählermaschine hat der RAM seine Anweisungen im Finite-State-Teil der Maschine (die sogenannten Harvard Architektur).

Das Äquivalent des Widders der Universelle Turing -Maschine- mit Programm in den Registern sowie deren Daten - wird als die genannt Zufälliger Zugriff gespeicherte Produktmaschine oder Raspe. Es ist ein Beispiel für das sogenannte Von Neumann Architektur und ist dem gemeinsamen Begriff a am nächsten Computer.

Zusammen mit dem Turing Maschine und GegenmaschinenmodelleDie RAM- und RASP -Modelle werden für verwendet Rechenkomplexitätsanalyse. Van Emde Boas (1990) nennt diese drei plus die Zeigermaschine Modelle "Sequentielle Maschine", um sie von "von" zu unterscheiden "Parallele Zufallszugriffsmaschine"Modelle.

Einführung in das Modell

Das Konzept von a Zufallszugriff Machine (RAM) beginnt mit dem einfachsten Modell von allen, dem sogenannten Zählermaschine Modell. Zwei Ergänzungen bewegen es jedoch von der Thekemaschine. Die erste verbessert die Maschine mit der Bequemlichkeit der indirekten Adressierung. Die zweite bewegt das Modell in Richtung des herkömmlichen Akkumulators basierend Computer Mit der Zugabe von einem oder mehreren Hilfsregistern (dedizierte) Register, von denen das häufigste als "Akkumulator" bezeichnet wird.

Formale Definition

A Zufallszugriffsmaschine (RAM) ist ein abstraktes Computational-Machine-Modell, das mit einem Mehrfachregister identisch ist Zählermaschine Mit indirekter Adressierung. Nach eigenem Ermessen der Unterricht durch seine endliche Zustandsmaschine's Tabelle, die Maschine leitet eine Adresse des "Ziel" -Regiens entweder (i) direkt aus der Anweisung selbst ab oder (ii) indirekt aus dem Inhalt (z. B. Nummer, Etikett) des in der Anweisung angegebenen "Zeiger" -register.

Per Definition: a registrieren ist ein Ort mit beiden die Anschrift (Eine einzigartige, unterscheidbare Bezeichnung/Locator entspricht einer natürlichen Zahl) und a Inhalt- Eine einzelne natürliche Zahl. Für die Präzision werden wir die Quasi-Formal-Symbolik von Boolos-Burgess-Jeffrey (2002) verwenden, um ein Register, seinen Inhalt und einen Betrieb in einem Register anzugeben:

[R] bedeutet "den Inhalt des Registers mit der Adresse R". Das Etikett "R" hier ist eine "Variable", die mit einer natürlichen Zahl oder einem Buchstaben (z. B. "a") oder einem Namen gefüllt werden kann.
→ bedeutet "Kopie/Einzahlung in" oder "ersetzt", jedoch ohne Zerstörung der Quelle

Beispiel: [3] +1 → 3; bedeutet "Der Inhalt des Quellregisters mit der Adresse" 3 "plus 1 wird mit Adresse" 3 "in das Zielregister gebracht (hier sind Quelle und Ziel der gleiche Ort). Wenn [3] = 37, dh der Inhalt von Register 3 ist die Zahl "37", dann wird 37+1 = 38 in Register 3 eingesetzt.

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

Definition: a Direkte Anweisung ist eine, die angibt in der Anweisung selbst Die Adresse des Quell- oder Zielregisters, dessen Inhalt Gegenstand der Anweisung sein wird. Definition: an Indirekte Anweisung ist eine, die ein "Zeigerregister" angibt, dessen Inhalt die Adresse eines "Ziel" -Registers ist. Das Zielregister kann entweder eine Quelle oder ein Ziel sein (die verschiedenen Kopieranweisungen geben hierbei Beispiele). Ein Register kann sich indirekt ansprechen.

Für Mangel an Standard/Konvention wird in diesem Artikel "Direct/Indirect" angegeben, das als "D/I" als Parameter (oder Parameter) in der Anweisung abgekürzt wird:

Beispiel: Kopie ( d, EIN, i, N) bedeutet direkt d Holen Sie sich die Adresse des Quellregisters (Registrieren Sie "A") aus der Anweisung selbst, aber indirekt i Holen Sie sich die Zieladresse von Zeigerregister N. Angenommen [n] = 3, dann ist registrieren 3 das Ziel und die Anweisung wird Folgendes erfolgen: [a] → 3.

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

Definition: der Inhalt der Zeigerregister ist der die Anschrift des "Ziel" Register.

Definition: der Inhalt der Zeigerregister zeigt auf die Zielregister- Das "Ziel" kann entweder eine Quelle oder ein Zielregister sein.

Definition: die Zielregister Dort lagert der Anweisungen ihr Ergebnis ab. Die Adresse des Quellregisters kann entweder (i) direkt durch die Anweisung oder (ii) indirekt durch das durch die Anweisung angegebene Zeigerregister angegeben werden. Die Quell- und Zielregister können eins sein.

Auffrischung: Das Counter-Machine-Modell

Melzak (1961) bietet eine einfache Visualisierung einer Zählermaschine: Die "Register" sind Löcher im Boden, und diese Löcher halten Kieselsteine. Gemäß Anweisungen in und aus diesen Löchern "Der Computer" (Person oder Maschine) fügt (Inkremente) oder Entfernungen (Dekremente) einen einzelnen Kiesel hinzu. Nach Bedarf kommen zusätzliche Kieselsteine aus und überschüssige Kieselsteine zurück in eine unendliche Versorgung; Wenn das Loch zu klein ist, um die Kieselsteine aufzunehmen, gräbt der "Computer" das Loch größer.

Minsky (1961) und Hopcroft-Ullman 1979 (S. 171) bieten die Visualisierung eines Multitaps Turing Maschine mit so vielen linken Bändern wie "Registern". Nach rechts ist die Länge jedes Bandes unbegrenzt und jedes Quadrat ist leer, bis auf das linke Ende, das gekennzeichnet ist. Das Distanz Von einem "Kopf" eines Bandes von seinem linken Ende, gemessen in Anzahl von Bandquellen, repräsentiert die natürliche Zahl in "The Register". Um die Anzahl der Quadrate zu verringern, bewegt sich der Klebebandkopf nach links; Inkrementiert es nach rechts. Es ist nicht erforderlich, Markierungen auf dem Band zu drucken oder zu löschen. Die einzigen bedingten Anweisungen sind zu prüfen, ob sich der Kopf am linken Ende befindet, indem eine linke Marke mit einer "Sprung-wenn-Marke-Anweisung" getestet wird.

Die folgende Anweisung "Mnemonics", z. "Clr (r)" sind willkürlich; Es gibt keinen Standard.

Das Registrieren Sie Maschine hat für einen Speicher außerhalb seiner Finite-State-Maschine-eine unbegrenzte (vgl.: Fußnote | zählbare und unbegrenzte) Sammlung diskreter und einzigartig beschrifteter Orte mit ungebunden Kapazität, "Register" genannt. Diese Register enthalten nur natürliche Zahlen (Null- und positive Ganzzahlen). Laut einer Liste der sequentiellen Anweisungen in der Tabelle der Finite -Status -Maschine arbeiten einige (z. B. 2) Arten von primitiven Operationen auf dem Inhalt dieser "Register". Endlich a Bedingungsexpression in Form eines If-then-else ist verfügbar, um den Inhalt von einem oder zwei Registern zu testen und die endliche Zustandsmaschine aus der Standardanweisungssequenz zu "Branche/Springen".

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

{Inkrementinhalt des Registers r, Dekrementinhalt des Registers r,, WENN Inhalt des Registers R ist Null DANN Springe zur Anweisung i_z ANDERS Fahren Sie mit dem nächsten Anweisungen fort}:

Anweisung	Mnemonisch	Aktion auf Register (en) "R"	Aktion zum Anweisungsregister der endlichen Zustandsmaschine, IR
Zuwachs	Inc (R)	[r] + 1 → r	[Ir] + 1 → ir
Abnahme	Dec (r)	[r] - 1 → r	[Ir] + 1 → ir
Springen Sie, wenn Null	JZ (R, Z)	keiner	If [r] = 0 dann z → ir sonst [ir] + 1 → ir
Halt	H	keiner	[Ir] → ir

Basismodell 2: Das "Nachfolger" -Modell (benannt nach der Nachfolgerfunktion der Peano -Axiome):

{Inkrementieren Sie den Inhalt des Registers r, löschen Sie den Inhalt des Registers r. WENN Inhalt des Registers r_j Entspricht dem Inhalt des Registers r_k DANN Springe zur Anweisung i_z ANDERS Geto zur nächsten Anweisung}

Anweisung	Mnemonisch	Aktion auf Register (en) "R"	Aktion zum Anweisungsregister 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 sonst [ir] + 1 → ir
Halt	H	keiner	[Ir] → ir

Basismodell 3: Wird von Elgot-Robinson (1964) bei der Untersuchung begrenzter und unbegrenzter RaSPs verwendet-das "Nachfolger" -Modell mit Kopie an der Stelle des Klares:

{Inkrementieren Sie den Inhalt des Registers r, kopieren Sie den Inhalt des Registers r_j zu registrieren r_k, WENN Inhalt des Registers r_j Entspricht dem Inhalt des Registers r_k dann Springe zur Anweisung i_z ANDERS Geto zur nächsten Anweisung}

Anweisung	Mnemonisch	Aktion auf Register (en) "R"	Aktion zum Anweisungsregister der endlichen Zustandsmaschine, IR
KOPIEREN	Kopie (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 sonst [ir] + 1 → ir
Halt	H	keiner	[Ir] → ir

Erstellen Sie "Convenience -Anweisungen" aus den Basissätzen

Die drei oben genannten Basissätze 1, 2 oder 3 sind in dem Sinne gleichwertig, dass man die Anweisungen eines Satzes unter Verwendung der Anweisungen eines anderen Satzes erstellen kann (eine interessante Übung: Ein Hinweis von Minsky (1967) - Deklary ein reserviertes Register, z. B. Anruf aufrufen Es "0" (oder z für "Null" oder E für "Erase"), um die Zahl 0 zu enthalten). Die Wahl des Modells hängt davon ab, welche ein Autor am einfachsten in einer Demonstration oder einem Beweis usw. verwendet wird.

Darüber hinaus können wir aus den Basissätzen 1, 2 oder 3 erstellen irgendein des primitive rekursive Funktionen (CF Minsky (1967), Boolos-Burgess-Jeffrey (2002)). (Wie man das Netz breiter wirkt, um das zu erfassen gesamt und teilweise MU rekursive Funktionen wird im Kontext der indirekten Adressierung erörtert). Das Aufbau der primitiven rekursiven Funktionen ist jedoch schwierig, da die Anweisungssätze so ... primitiv (winzig) sind. Eine Lösung besteht darin, einen bestimmten Satz mit "Convenience -Anweisungen" aus einem anderen Satz zu erweitern:

Diese werden nicht im konventionellen Sinne Subroutinen sein, sondern eher Blöcke von Anweisungen aus dem Basissatz und einer mnemonischen. In formaler Sinne müssen wir diese Blöcke entweder (i) in ihre Basis-Instruktionsäquivalente "erweitern"-sie benötigen die Verwendung von temporären oder "Hilfsregistern", damit das Modell dies berücksichtigen muss oder ((((( ii) Entwerfen Sie unsere Maschinen/Modelle mit den Anweisungen 'eingebauter'.

Beispiel: Basissatz 1. Um CLR (R) zu erstellen, verwenden Sie den Anweisungsblock, um das Register R auf Null zu zählen. Beobachten Sie die Verwendung des oben genannten Hinweiss:

Clr (r) =_Äquiv
Schleife: JZ (r, Ausfahrt)

Dec (r)
JZ (0, Schleife)

Ausfahrt: etc.

All dies dient wieder nur aus Gründen der Bequemlichkeit; Nichts davon erhöht die intrinsische Kraft des Modells.

Zum Beispiel: Der am meisten erweiterte Set umfasst jede eindeutige Anweisung aus den drei Sätzen sowie bedingungslosen Sprung j (z), d. H. H.:

{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 das eine oder andere der bedingten Sprünge, z. Shepherdson-Sturgis (1963) Verwenden Sie das obige Set minus JE (um perfekt genau zu sein, verwenden sie JNZ-springen Sie wenn Nicht Null anstelle von JZ; Noch eine mögliche Komfortanweisung).

Die "indirekte" Operation

Beispiel für die indirekte Adressierung

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

Beispiel: Eine Schatzsuche.

An der Stelle "Tom _ & _ Becky's_cave_in_pirate_chest" werden wir eine Karte finden, die uns auf "den Schatz" leitet:

(1) Wir gehen zu Ort "Tom _ & _ Becky's_cave ..." und graben herum, bis wir eine Holzkiste finden

(2) In der Box befindet sich eine Karte zum Ort des Schatzes: "Under_thatcher's_front_porch"

.

Indirektion Gibt einen Ort an, der als Piratenkiste in "Tom _ & _ Becky's_cave ..." identifiziert wurde, der als Zeiger an einen anderen Ort (einschließlich sich selbst): Der Inhalt (die Schatzkarte) liefert die "Adresse" der Ziel Ort "Under_Thatcher's_front_porch", wo die reale Aktion stattfindet.

Warum die Notwendigkeit eines indirekten Betrieb

Im Folgenden muss man sich daran erinnern, dass diese Modelle abstrakte Modelle mit zwei grundlegenden Unterschieden von allem physisch Real sind: unbegrenzte Anzahl von Registern mit unbegrenzten Kapazitäten. Das Problem erscheint am dramatischsten, wenn man versucht, ein Counter-Machine-Modell zu verwenden, um eine Raspe zu erstellen, die ist Äquivalent und somit alle teilweise berechnen MU rekursive Funktion:

Melzak (1961) fügte sein Modell "Hole-and-Pebble" -Modell hinzu, so dass sein Modell sich mit einem "berechneten Goto" modifizieren konnte und zwei Beispiele für seine Verwendung liefert ("Dezimalrepräsentation im Maßstab von D" und "Sortieren durch Größe ", ob diese in seinem Beweis dafür verwendet werden, dass das Modell ein äquivalent ist, ist unklar, da" das Programm selbst dem Leser als Übung überlassen wird "(S. 292)). Minsky (1961, 1967) konnte nachweisen, dass dies mit geeignetem (aber schwer zu bedienender) Gödel -Nummer Codierung musste das Registermodell keine Indirektion mussten, um gleichwertig zu sein. Aber es brauchte mindestens ein unbegrenztes Register. Wie unten erwähnt, deutet Minsky (1967) auf das Problem für eine Raspe hin, bietet aber keine Lösung. Elgot und Robinson (1964) haben bewiesen, dass ihr RASP -Modell P.₀- Es hat keine Indirektion Fähigkeit - nicht alle "rekursiven sequentiellen Funktionen" (solche mit einer willkürlichen Länge), wenn es nicht die Fähigkeit hat, seine eigenen Anweisungen zu ändern, aber es kann über Gödel -Zahlen können (S. 395) (S. 395) -397; insbesondere Abbildung 2 und Fußnote S. 395). Andererseits ihr Rasp -Modell P '₀ Ausgestattet mit einem "Indexregister" (indirekte Adressierung) kann alle "partiellen rekursiven sequentiellen Funktionen" (die rekursiven Funktionen der MU) (S. 397-398) berechnen.

Cook und Reckhow (1973) sagen es am kurzsten:

Die indirekten Anweisungen sind erforderlich, damit ein festes Programm auf eine unbegrenzte Anzahl von Registern zugreift, wenn die Eingaben variieren. "(S. 73).

Ungebunden Kapazitäten von Registern versus begrenzte Kapazitäten der Anweisungen der Staatsmaschine: Die sogenannte endlich Zustandsteil der Maschine soll - nach der normalen Definition von Algorithmus - sein - sehr endlich sowohl in der Anzahl der "Zustände" (Anweisungen) als auch in den Größen der Anweisungen (ihre Fähigkeit, Symbole/Zeichen zu halten). Wie bewegt eine Zustandsmaschine eine willkürlich große Konstante direkt in ein Register, z. Move (k, r) (Bewegung Konstante K, um R zu registrieren)? Wenn riesige Konstanten erforderlich sind, müssen sie entweder in den Registern selbst beginnen oder von der Staatsmaschine unter Verwendung einer begrenzten Anzahl von Anweisungen erstellt werden, z. Multiplizieren Sie und fügen Sie Unterprogramme mit Inc und DEC hinzu (aber nicht eine quasi-infinite Anzahl dieser!).

Manchmal wird die Konstante k unter Verwendung von CLR (R) erzeugt, gefolgt von INC (R) wiederholt K -Zeiten - z. Um die Konstante k = 3 in das Register r zu setzen, d. H. 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 tritt auf endlich Zustandsmaschine; Es gibt immer eine größere Konstante als die Anzahl der Anweisungen, die dem verfügbar sind endlich Zustandsmaschine.

Ungebunden Zahlen von Registern gegen begrenzte Anweisungen zur Staatsmaschine: Dies ist schwerwiegender als das erste Problem. Insbesondere entsteht dieses Problem, wenn wir versuchen, eine sogenannte Raspe, eine "universelle Maschine", zu erstellen (siehe More at Universelle Turing -Maschine) Das nutzt seine Finite-State-Maschine, um ein "Anweisungsprogramm" in seinen Registern zu interpretieren-d. H. Wir bauen das, was heutzutage genannt wird Computer mit dem Von Neumann Architektur.

Beachten Sie, dass die endliche Zustandsmaschine der Zählermaschine ein Register aufrufen muss ausdrücklich (Direkt) mit Namen/Nummer: Inc (65.356) Rufe die Registernummer "65.365" auf ausdrücklich. Wenn die Anzahl der Register die Fähigkeit des endlich Statusmaschine, um sie anzusprechen, sind Register außerhalb der Grenzen nicht erreichbar. Zum Beispiel, wenn die endliche Zustandsmaschine nur 65.536 = 2 erreichen kann¹⁶ Register wie kann es dann den 65.537. erreichen?

Also wie tun Wir sprechen ein Register über die Grenzen der endlichen Zustandsmaschine hinaus? Ein Ansatz wäre, die zu ändern Programm-Instrukturen (die in den Registern gespeicherten), so dass sie mehr als einen Befehl enthalten. Dies kann jedoch auch erschöpft werden, es sei denn, eine Anweisung besteht aus (möglicherweise) unbegrenzter Größe. Warum also nicht nur eine "Über-Instruktion" verwenden-eine wirklich große Zahl-, die enthält alle Die Programmanweisungen wurden darin eingeteilt! So löst Minsky das Problem, aber das Gödel -Nummerierung Er verwendet eine große Unannehmlichkeit für das Modell, und das Ergebnis ist gar nichts wie unsere intuitive Vorstellung eines "gespeicherten Programmcomputers".

Elgot und Robinson (1964) kommen zu einer ähnlichen Schlussfolgerung in Bezug auf eine Raspe, die "endlich bestimmt" ist. In der Tat kann es auf eine unbegrenzte Anzahl von Registern zugreifen (z. B. um Anweisungen von ihnen abzurufen), aber nur, wenn die Raspe "Selbstveränderung" zulässt Programm Anweisungen und hat seine "Daten" in einer Gödel -Zahl codiert (Abb. 2 S. 396).

Im Zusammenhang mit einem computerähneren Modell unter Verwendung seines RPT (Repeat)-Anweisungen verspottet uns Minsky (1967) eine Lösung für das Problem (vgl. S. 214, S. 259), bietet jedoch keine feste Auflösung. Er behauptet:

"Im Allgemeinen könnte ein RPT-Betrieb keine Anweisung im Finite-State-Teil der Maschine sein ... Dies kann eine bestimmte Menge an Speicher ausschöpfen, die im endlichen Teil des Computers zulässig ist [sic, sein Name für seine RAM-Modelle]. RPT -Operationen erfordern eigene unendliche Register. " (S. 214).

Er bietet uns eine an begrenzt Rpt können zusammen mit CLR (R) und Inc (R) jeden berechnen primitive rekursive Funktionund er bietet die oben angegebene unbegrenzte RPT an, die die Rolle des μ -Operators spielt; Es können zusammen mit CLR (R) und Inc (R) die rekursiven MU -Funktionen berechnen. Aber er diskutiert weder "Indirektion" noch das RAM -Modell an sich.

Aus den Referenzen in Hartmanis (1971) scheint Cook (in seinen Vorlesungsnotizen in der UC Berkeley, 1970) den Begriff der indirekten Adressierung festzulegen. Dies wird im Papier von Cook and Reckhow (1973) klarer - Cook ist Reckhows Master -Theseberater. Das Modell von Hartmanis-das Modell von Melzak (1961) ziemlich ähnlich-verwendet zwei und drei Register-Adds und subtrahiert und zwei Parameterkopien. Das Modell von Cook und Reckhow reduziert die Anzahl der Parameter (Register, die in den Programmanweisungen aufgefordert werden) auf einen Call-out unter Verwendung eines Akkumulators "AC".

Die Lösung in der Phase von Phasen: Entwerfen Sie unser Maschinen-/Modell mit Unbundgebundenen Indirektion- anbieten ungebunden "Adresse" Register, das möglicherweise ein Register benennen kann, unabhängig davon, wie viele es gibt. Damit dies im Allgemeinen funktioniert, die ungebunden Das Register erfordert die Fähigkeit, gelöscht und dann durch eine potenziell unendliche Schleife inkrementiert (und möglicherweise dekrementiert) zu werden. In diesem Sinne repräsentiert die Lösung die Unbundigen μ -Operator Das kann bei Bedarf ad Infinitim entlang der unbegrenzten Registerkette jagen, bis es findet, wonach es sucht. Das Zeigerregister ist genau wie jedes andere Register mit einer Ausnahme: Unter den Umständen, die als "indirekte Adressierung" bezeichnet werden, bietet es es zur Verfügung es ist Inhalt und nicht der Adress-Operand in der Tabelle der Statusmaschine, um die Adresse des Zielregisters zu sein (einschließlich möglicherweise selbst!).

Begrenzte Indirektion und die primitiven rekursiven Funktionen

Wenn wir den Minsky -Ansatz einer Monsternummer in einem Register meiden und angeben, dass unser Maschinenmodell "wie ein Computer" ist μ-rekursive Funktionen ) - Sowohl Gesamt- als auch teilweise Sorten.

Unser einfacheres Counter-Machine-Modell kann eine "begrenzte" Form der Indirektion ausführen-und dadurch die Unterklasse von berechnen primitive rekursive Funktionen-Durch die Verwendung eines primitiven rekursiven "Operators" genannt "Definition nach Fällen" (definiert in Kleene (1952) S. 229 und Boolos-Burgess-Jeffrey S. 74). Eine solche "begrenzte Indirektion" ist eine mühsame, mühsame Angelegenheit. "Definition nach Fällen" verlangt von der Maschine, den Inhalt des Zeigerregisters durch Versuch zu bestimmen/zu unterscheiden, um diesen Inhalt mit einer Nummer/einem Namen zu entsprechen, die der Fallbetreiber ausdrücklich erklärt. Somit beginnt die Definition durch Fälle aus z. Die untere gebundene Adresse und ad nauseam in Richtung der oberen gebundenen Adresse, die versucht, eine Übereinstimmung zu treffen:

Ist die Zahl in Register n gleich 0? Wenn nicht, ist es gleich 1? 2? 3? ... 65364? Wenn nicht, sind wir auf der letzten Nummer 65365 und das sollte besser sein, sonst haben wir ein Problem!

"Begrenzte" Indirektion erlaubt uns nicht, die teilweise rekursiven Funktionen zu berechnen - für diejenigen, die wir brauchen ungebunden Indirektion alias das μ -Operator.

Angenommen, wir konnten auf Nummer 65367 weitermachen, und in der Tat hatte das Register das, wonach wir suchten. Dann hätten wir unsere Berechnung erfolgreich erledigen können! Angenommen, 65367 hatte nicht das, was wir brauchten. Wie weit sollten wir weiterhin gehen?

Sein Äquivalent Die Zählermaschine muss entweder den unglücklichen Single-Register-Minsky verwenden Gödel -Nummer Methode oder erweitert mit der Fähigkeit, die Enden seiner Register -Zeichenfolge zu untersuchen, falls erforderlich. (Ein Versäumnis, etwas "da draußen" zu finden, definiert, was es bedeutet, dass ein Algorithmus nicht beendet wird; vgl. KAPITEL XII Partial rekursive Funktionen, insbesondere p. 323-325.) Weitere Informationen finden Sie im Beispiel unten.

Unbegrenzte Indirektion und die teilweise rekursiven Funktionen

Zum ungebunden Indirektion Wir benötigen eine "Hardware" -Veränderung in unserem Maschinenmodell. Sobald wir diese Änderung vorgenommen haben, ist das Modell keine Zählermaschine mehr, sondern eine zufällige Maschine.

Nun, wenn z. Inc ist angegeben, die Anweisung der endlichen Zustandsmaschine muss angeben wo Die Adresse des Interessenregisters kommt von. Dies wo kann entweder (i) der Anweisungen der Zustandsmaschine sein, der eine liefert Explizite Etikett, oder (ii) die Zeigerregister Deren Inhalt ist die Ansprache von Interesse. Immer wenn eine Anweisung eine Registeradresse angibt, wird diese jetzt angegeben Auch müssen einen zusätzlichen Parameter "i/d" - "indirekt/direkt" angeben. In gewissem Sinne ist dieser neue "I/D" -Parameter ein "Switch", der eine Möglichkeit dreht, die direkte Adresse wie in der Anweisung angegeben oder die andere Möglichkeit zu erhalten, um die indirekte Adresse aus dem Zeigerregister (welches Zeigerregister - in einigen Modelle Jedes Register kann ein Zeigerregister sein - wird durch die Anweisung angegeben. Diese "gegenseitig ausschließliche, aber erschöpfende Wahl" ist ein weiteres Beispiel für "Definition nach Fällen", und das im folgende Beispiel gezeigte arithmetische Äquivalent wird aus der Definition in Kleene (1952) p abgeleitet. 229.

Beispiel: CPY (indirekt_Quelle, r_Quelle, Direkte_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 bestimmen:

i*[r_s] + (1-i)*r_s

Nehmen wir beispielsweise an, der Inhalt des Registers 3 ist "5" (d. H. [3] = 5) und der Inhalt des Registers 4 "2" (d. H. [4] = 2):

Beispiel: CPY (1, 3, 0, 4) = CPY (indirekt, Reg 3, Direkt, Reg 4)

1*[3] + 0*3 = [3] = Quellregister-Adresse 5

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

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

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

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

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

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

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

Die indirekte Kopieranweisung

Die wahrscheinlich nützlichste der zusätzlichen Anweisungen ist die Kopie. In der Tat stellt Elgot-Robinson (1964) ihre Modelle P zur Verfügung p₀ und P'₀ Mit den Kopieranweisungen und Cook-Reckhow (1973) geben ihr akkumulatorbasiertes Modell nur zwei indirekte Anweisungen an-kopieren Sie indirekt auf Akkumulator und kopieren Sie indirekt vom Akkumulator.

Eine Fülle von Anweisungen: Da jede Anweisung, die auf ein einzelnes Register einwirkt, durch seine indirekte "Dual" (einschließlich bedingter und bedingungsloser Sprünge, vgl. Das Elgot-Robinson-Modell), wird die Einbeziehung indirekter Anweisungen die Anzahl der einzelnen Parameter-/Registeranweisungen verdoppelt (z. Inc (D, R), Inc (I, R)). Schlimmer noch, alle beiden Parameter-/Registeranweisungen haben 4 mögliche Sorten, z. B.:

CPY (d, r_s, DR_d ) = Kopieren Sie direkt von der Quellregister direkt zum Zielregister

Cpy (i, r_sp, DR_d ) = Kopieren Sie indirekt auf das Zielregister mit der Quelladresse, die im Quell-Zeiger-Register R gefunden werden soll_sp.

CPY (d, r_s, i, r_dp ) = Inhalt von Quellenregister indirekt in das Register mit der Zieladresse kopieren, um im Ziel-Einzeiger-Register R zu finden_dp.

Cpy (i, r_sp, i, r_dp ) = Indirekt kopieren Sie den Inhalt des Quellregisters mit der Adresse, die im Quell-Zeiger-Register r zu finden ist_sp, in das Zielregister mit der Adresse, die im Ziel-Zeigerregister zu finden ist_dp)

In ähnlicher Weise jede Dreierregistrierungsanweisung, die zwei Quellregister beinhaltet r_S1 r_S2 und ein Zielregister r_d führt zu 8 Sorten, zum Beispiel die Zugabe:

[r_S1] + [r_S2] → r_d

wird nachgeben:

Add (d, r_S1, DR_S2, DR_d )
Add (i, r_SP1, DR_S2, DR_d )
Add (d, r_S1, i, r_sp2, DR_d )
Add (i, r_SP1, i, r_sp2, DR_d )
Add (d, r_S1, DR_S2, i, r_dp )
Add (i, r_SP1, DR_S2, i, r_dp )
Add (d, r_S1, i, r_sp2, i, r_dp )
Add (i, r_SP1, i, r_sp2, i, r_dp )

Wenn wir ein Register als "Akkumulator" bezeichnen (siehe unten) und die verschiedenen zulässigen Anweisungen starke Einschränkungen einlegen, können wir die Fülle von direkten und indirekten Operationen erheblich reduzieren. Man muss jedoch sicher sein, dass das resultierende reduzierte Anweisungssatz ausreichend ist, und wir müssen uns bewusst sein, dass die Reduzierung auf Kosten mehr Anweisungen pro "erheblicher" Betrieb erfolgt.

Der Begriff von "Akkumulator a"

Die historische Konvention widmet dem Akkumulator ein Register, ein "arithmetisches Organ", das seine Anzahl während einer Abfolge von arithmetischen Operationen buchstäblich ansammelt:

"Der erste Teil unseres arithmetischen Organs ... sollte ein paralleles Speicherorgel sein, das eine Nummer empfangen und zu dem bereits darin fügt, was auch in der Lage ist, ihren Inhalt zu löschen und das zu speichern, was es enthält. Wir werden werden Nennen Sie eine solche Orgel und Akkumulator. Es ist im Prinzip in früheren und gegenwärtigen Computermaschinen der unterschiedlichsten Typen, z. Desk -Multiplikatoren, Standard -IBM -Zähler, modernere Relaismaschinen, The Eniac "(BOLDFACE In Original: Goldstine und von Neumann, 1946; S. 98 in Bell und Newell 1971).

Der Akkumulator geht jedoch auf Kosten weiterer Anweisungen pro arithmetischer "Operation", insbesondere in Bezug auf das, was als "Read-Modify-Write" -Anweisungen bezeichnet wird, wie "indirekt den Inhalt des Registers durch Register R2 inkrementiert". "A" bezeichnet den "Akkumulator" Register a:

Etikett	Anweisung	EIN	R2	R378,426	Beschreibung
		. . .	378,426	17
INCI (R2):	Cpy (i, r2, d, a)	17	378,426	17	Inhalt von R2 Punkten auf R378.426 mit Inhalt "17": Kopieren Sie dies zu a
	Inc (a)	18	378,426	17	Incement -Inhalt von a
	CPY (D, A, I, R2)	18	378,426	18	Inhalt von R2 Punkten auf R378,426: Kopieren von Inhalten von A in R378.426 kopieren

Wenn wir uns an einen bestimmten Namen für den Akkumulator halten, z. "A", wir können den Akkumulator beispielsweise in den Anweisungen implizieren,

Inc (a) = Inca

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

CPY (d, r2, d, a) = cpy (d, r2,,)

CPY (D, A, D, R2) = CPY (, D, R2)

Historisch gesehen hat diese beiden CPY -Anweisungen unverwechselbare Namen erhalten. Es gibt jedoch keine Konvention. Tradition (z. Knuth's (1973) imaginär MISCHEN Computer) verwendet zwei Namen, die als Last und Speicher bezeichnet 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 verfügt über alle zwei Variablen arithmetischen und konstanten Operationen (z. B. add (a, r), sub (a, r)) Verwenden Sie (i) den Inhalt des Akkumulators zusammen mit (ii) den Inhalt eines angegebenen Registers . Die Ein-Variablen-Operationen (z. B. inc (a), dec (a) und clr (a)) erfordern nur den Akkumulator. Beide Anweisungen werden das Ergebnis (z. B. Summe, Differenz, Produkt, Quotienten oder Rest) im Akkumulator hinterlegt.

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ählen, können wir die Mnemonik abkürzen, da mindestens ein Quellregister und das Zielregister immer der Akkumulator A sind. Daher 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 eine hat Unbegrenzter Akkumulator können wir gebunden Alle anderen Register? Erst wenn wir mindestens ein unbegrenztes Register sorgen, aus dem wir unsere indirekten Adressen ableiten.

Der minimalistische Ansatz besteht darin, sich selbst zu verwenden (Schönhage tut dies).

Ein anderer Ansatz (auch Schönhage) besteht darin, ein bestimmtes Register das "indirekte Adressregister" zu deklarieren und die Indirektion in Bezug auf dieses Register einzuschränken (das RAM0 -Modell von Schonhage verwendet sowohl A- als auch N -Register für indirekte und direkte Anweisungen). Auch hier hat unser neues Register keinen herkömmlichen Namen - vielleicht "n" aus "Index" oder "indirekt" oder "Adressnummer".

Für maximale Flexibilität, wie wir es für den Akkumulator A getan haben-werden wir N nur ein anderes Register betrachten, das in Erkrankung, Dekrement, Löschen, Test, direkter Kopie usw. unterliegt und zum Beispiel Indirektion.

Ldan (i/d) = cpy (i/d, n, d, a); Laden des Akku über Indirektion Register laden

Stan (i/d) = cpy (d, a, i/d, n). Speichern der Akkumulator über Indirektion Register

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

(1) Ein Befehlssatz ohne Parameter:

Schönhage produziert seinen RAM0 -Anweisungssatz. Siehe Abschnitt unten.

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

Als Minimalisten reduzieren wir alle Register mit Ausnahme des Akkumulators A und des Indirektion Register N, z. r = {r0, r1, r2, ...} zu einer unbegrenzten Reihe von (sehr) Taubenlözen mit begrenzter Kapazität. Diese werden nichts anderes tun, als (sehr) begrenzte Zahlen zu halten, z. Ein einsames Bit mit Wert {0, 1}. Ebenso verkleinern wir den Akkumulator auf ein einzelnes Bit. Wir beschränken alle Arithmetik auf die Register {a, n}, verwenden indirekte Operationen, um den Inhalt der Register in den Akkumulator zu ziehen und 0 oder 1 aus dem Akkumulator in ein Register zu schreiben:

{Lda (i, n), sta (i, n), clr (a/n), inc (a/n), dec (n), jz (a/n, i_z), JZ (i_z), H }

Wir drücken weiter und beseitigen einen insgesamt durch die Verwendung von zwei "konstanten" Registern, die als "Löschen" und "Print" bezeichnet werden: [Erase] = 0, [Druck] = 1.

{Cpy (d, erase, i, n), cpy (d, print, i, n), clr (n), Inc (n), dec (n), jz (i, n, i_z), JZ (i_z), H }

Benennen Sie die Kopieranweisungen um und rufen Sie inc (n) = rechts, dec (n) = links auf und wir haben die gleichen Anweisungen wie die Nach-Turing-Maschine sowie ein zusätzliches CLRN:

{Löschen, drucken, clrn, rechts, links, jz (i, n, ich_z), JZ (i_z), H }

Turing -Äquivalenz des Widders in der Indirektion

In dem obigen Abschnitt haben wir informell gezeigt, dass ein RAM mit einer unbegrenzten Indirektion einen erzeugt Post -Turing -Maschine. Die Post -Turing -Maschine ist ein äquivalentes Turing, sodass wir gezeigt haben, dass der RAM mit Indirektion äquivalent ist.

Wir geben hier eine etwas formellere Demonstration. Entwerfen Sie unser Modell mit drei reservierten Registern "e", "p" und "n" sowie einen unbegrenzten Satz von Registern 1, 2, ..., n rechts. Die Register 1, 2, ..., n werden als "die Quadrate des Bandes" angesehen. Registrieren Sie sich "n" auf "das gescannte Quadrat", dass "The Head" derzeit beobachtet. Der "Kopf" kann als im bedingten Sprung angesehen werden-beobachten Sie, dass er indirekte Adressierung verwendet (cf Elgot-Robinson S. 398). Wenn wir "n" nementieren oder inkrementieren, bewegt sich der (scheinbare) Kopf "links" oder "rechts" entlang der Quadrate. Wir werden den Inhalt von "e" = 0 oder "P" = 1 auf das "gescannte Quadrat", wie durch N unter Verwendung der indirekten CPY, verschieben.

Die Tatsache, dass unser Klebeband links in der Linken ist, stellt ein kleines Problem dar: Immer wenn die Anleitung auftritt, müssen unsere Anweisungen getestet werden, um festzustellen, ob der Inhalt von "n" Null ist oder nicht; In diesem Fall sollten wir seine Zählung bei "0" verlassen (dies ist unsere Wahl als Designer - zum Beispiel könnten wir die Maschine/das Modell "ein Ereignis auslösen" unserer Wahl).

Anweisungssatz 1 (Augmented): {Inc (n), dec (n), clr (n), cpy (d, r_s, i, n), jz (i, r, z), halt}

Die folgende Tabelle definiert beide Anweisungen nach der Turation in Bezug auf ihre RAM-Äquivalentanweisungen und gibt ein Beispiel für ihre Funktionen. Die (scheinbare) Position des Kopfes entlang des Bandes der Register R0-R5. . . wird beschattet:

Mnemonisch	Etikett:		E	P	N	R0	R1	R2	R3	R4	R5	usw.	Aktion auf Register	Aktion auf endliche Staatsmaschinenanweisung Register IR IR

	Anfang:		0	1	3				1	0

R	Rechts:	Inc (n)	0	1	4				1	0			[N] +1 → n	[Ir] +1 → ir

P	drucken:	CPY (D, P, I, N)	0	1	4				1	1			[P] = 1 → [n] = R4	[Ir] +1 → ir

E	löschen:	CPY (D, E, I, N)	0	1	4				1	0			[E] = 0 → [n] = R4	[Ir] +1 → ir

L	links:	JZ (i, n, Ende)	0	1	4				1	0			keiner	WENN N = r4] = 0 dann "end" → ir sonst [ir] +1 → ir
		Dec (n)	0	1	3				1	0			[N] -1 → n

J0 (Halt)	Jump_if_Blank:	JZ (i, 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 (I, 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 gleichwertig ist

Während dieser Demonstration müssen wir berücksichtigen, dass die Anweisungen in der Tabelle der endlichen Zustandsmaschine sind begrenzt, d.h. endlich:

"Abgesehen davon, dass nur ein bloß ein ist Finite -Set von Regeln Dies ergibt eine Abfolge von Operationen zur Lösung eines bestimmten Problemtyps, ein Algorithmus hat fünf wichtige Merkmale [Finitimess, Bestimmung, Eingabe, Ausgabe, Effektivität] "(Italics hinzugefügt, Knuth S. 4-7).

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

Wir werden die indirekte CPY (i, q, d, φ) mit dem Falloperator bauen. Die Adresse des Zielregisters wird durch den Inhalt des Registers "Q" angegeben. Sobald der Fallbetreiber festgelegt hat, wie diese Zahl ist, wird CPY den Inhalt des Registers mit dieser Nummer direkt in das Register "φ" ablegt. Wir brauchen ein zusätzliches Register, das wir "Y" nennen werden-es dient als Aufwärtstrend.

Das Folgende ist also tatsächlich eine konstruktive Demonstration oder ein Beweis dafür, dass wir tatsächlich die indirekte CPY (i, q, d, φ) ohne eine "Hardware" -Designänderung an unserem Zähler-/Modell simulieren können. Beachten Sie jedoch, dass eine Raspe mit dieser indirekten CPY nur die Raspe mit dieser indirekten CPY nur berechnen kann primitive rekursive Funktionen, nicht die volle Suite von MU rekursive Funktionen.

Der Fall "Operator" wird in Kleene (1952) (S. 229) und in Boolos-Burgess-Jeffrey (2002) (S. 74) beschrieben; Die letzteren Autoren betonen seinen Nutzen. Die folgende Definition ist pro Kleene, aber modifiziert, um die vertraute "if-then-else" -Konstruktion widerzuspiegeln.

Der Fallbetreiber "gibt" eine natürliche Zahl in φ zurück, je nachdem, welcher "Fall" erfüllt ist, beginnend mit "case_0" und nacheinander durch "case_last"; Wenn kein Fall erfüllt ist, wird die Nummer "Standard" (auch bekannt als "Woops") in φ (hier hier zurückgegeben x bezeichnet eine Auswahl von Parametern, z. Register Q und die Zeichenfolge R0, ... rlast)):

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

case_0: wenn q₀(x, y) ist wahr, dann φ₀(x, y) sonst
case_1: wenn q₁(x, y) ist wahr, dann φ₁(x, y) sonst
cases_2 über case_next_to_last: etc.. . . . . . . . ANDERS
case_last: wenn q_letzte(x, y) ist wahr, dann φ_letzte(x, y) sonst
Standard: Do φ_{Ursprünglich}(x, y)

Kleene verlangt, dass die "Prädikate" q_n dass die Tests alle gegenseitig ausschließt - "Prädikate" sind Funktionen, die nur {true, false} für die Ausgabe erzeugen; Boolos-Burgess-Jeffrey fügt die Anforderung hinzu, dass die Fälle "erschöpfend" sind.

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

Definition nach Fällen Cpy (i, q, d, φ) =_def φ (q, r0, ..., rlast, y) =

case_0: wenn clr (y), [q] - [y] = 0 dann cpy (r0, φ), j (exit) else sonst
case_1: Wenn Inc (y), [q] = [y] = 1 dann cpy (r1, φ), j (exit) else sonst
case_2 über Fall N: if. . . DANN . . . ANDERS
case_n: Wenn Inc (y), [q] = [y] = n dann cpy (rn, φ), j (exit) else sonst
case_n+1 bis case_last: if. . . DANN . . . ANDERS
case_last: wenn inc (y), [q] = [y] = "last" dann cpy (rlast, φ), j (exit) sonst
Standard: Woops

Case_0 (der Grundschritt der Rekursion auf Y) sieht folgendermaßen aus:

case_0:

Clr (y); Setzen Sie Register y = 0
JE (Q, Y, _φ0 )
J ( Fall 1 )

_φ0: CPY (R0, φ)
J ( Ausfahrt )

Fall 1: usw.

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

case_n:

Inc (y)
JE (Q, Y, _φn )
J ( case_n+1)

_φn: CPY (RN, φ)
J ( Ausfahrt )

case__n+1: usw.

Case_Last stoppt die Induktion und begrenzt den Fallbetreiber (und begrenzt damit den Operator "Indirekter Kopie"):

case_last:

Inc (y)
JE (Q, Y, _φlast )
J ( woops )

_φlast: Cpy (rlast, φ)
J ( Ausfahrt )

woops: Wie gehen wir mit einem außerhalb der Untersuchungen versuchten Versuch um?
Ausfahrt: usw.

Wenn der Fall ad infinitum fortsetzen könnte, wäre es das MU -Betreiber. Aber es kann nicht - das "Zustandsregister der endlichen Zustandsmaschine" hat seine maximale Anzahl erreicht (z. B. 65365 = 1111111111111111111111₂ ) oder sein Tisch hat die Anweisungen ausgeht; es ist ein endlich Maschine schließlich.

Beispiele für Modelle

Modell von Register-Register ("Read-Modify-Write") von Cook and Reckhow (1973)

Das häufig auftretende Koch- und Aufladungsmodell ist ein bisschen wie das ternärische Malzek-Modell (geschrieben mit Knuth Mnemonics-die ursprünglichen Anweisungen hatten keine Mnemonik mit Ausnahme von TRA, Lesen, Druck).

Last (c, rd); C → Rd, C ist jede Ganzzahl

Beispiel: Laden (0, 5) wird das Register löschen 5.

Add (rs1, rs2, rd); [rs1] + [rs2] → rd, die Register können gleich oder anders sein;

Beispiel: Hinzufügen (a, a, a) wird den Inhalt des Registers A verdoppeln. A.

Sub (rs1, rs2, rd); [rs1] - [rs2] → rdDie Register können gleich oder anders sein:

Beispiel: Sub (3, 3, 3) wird Register 3 löschen 3.

Kopie (i, rp, d, rd); [[RP]] → RdKopieren Sie indirekt den Inhalt des Quellenregister_p in das Zielregister.
Kopie (d, rs, i, rp); [Rs] → [RP]. Kopieren Sie den Inhalt des Quellregisters r_s in das Zielregister, auf das der Zeigerregister r zeigt_p.
Jnz (r, iz); Bedingter Sprung, wenn [r] positiv ist; d. H. Wenn [R]> 0 dann zu Anweisungen springen Z, sonst fortzufahren (Cook und Reckhow nennen Sie Folgendes: "Übertragen Sie die Steuerung in Zeile m, wenn xj> 0").
Read (Rd); Kopieren Sie "die Eingabe" in das Zielregister r_d
Print (rs); Kopieren Sie den Inhalt des Quellregisters r_s zu "die Ausgabe".

Schönhages Ram0 und Ram1 (1980)

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

"Um zu vermeiden, dass ein explizites Adressierung des RAM0 den Akkumulator mit Inhalten hat z und ein zusätzliches Adressregister mit aktuellen Inhalten n (anfangs 0) "(S. 494)

RAM1 -Modell: Schönhage zeigt, wie seine Konstruktion verwendet werden kann, um die häufigere, verwendbarere Form des "Nachfolger" -ähnlichen 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; direkt laden a
Lda (i, r); [[R]] → A; indirekt laden a
Sta (d, r); [A] → R; direkt speichern a
Sta (i, r); [A] → [r]; indirekt speichern a
Jea (r, z); Wenn [a] = [r] dann geht ich sonst weiter
Inka; [A] + 1 -> a

RAM0 -Modell: Schönhages RAM0 -Maschine hat 6 Anweisungen, die durch einen einzelnen Buchstaben angegeben sind (das 6. "C xxx" scheint 'überspring über den nächsten Parameter' zu sein. Schönhage bezeichnet den Akkumulator mit "z", "n" mit "n" usw. als mit "n" usw. Schönhages Mnemonik Wir werden die oben entwickelten Mnemonik verwenden.

(Z), clra: 0 → a
(A), Inca: [a] +1 → a
(N), cpyan: [a] → n
(A), ldaa: [a]] → a ; Inhalt einer Punkte zur Registrierung der Adresse; Geben Sie den Inhalt des Registers in a
(S), Stan: [a] → [n] ; Inhalt von Npunkten, um die Adresse zu registrieren; Geben Sie den Inhalt von A in das Register ein, auf das von n vermerkt ist
(C), jaz (z): [a] = 0 dann gehen Sie zu iz ; mehrdeutig in seiner Behandlung

Indirektion kommt (i) von CPyan (Kopier-/Übertragungsinhalt A bis N) Arbeiten mit Store_A_VIA_N Stan und aus (ii) der besonderen Indirektionanweisung LDAA ([[a]] → [a]).

Fußnoten

Endlich gegen unbegrenzt

Die Definition der Tatsache, dass jede Art von Zählermaschine ohne unbegrenztes Register- "Adresse" Register ein Register "R" mit dem Namen angeben muss, zeigt an, dass das Modell "r" erforderlich ist endlich, obwohl es in dem Sinne "unbegrenzt" ist, dass das Modell keine Obergrenze für die Anzahl der Register impliziert, die für seine Arbeit erforderlich sind. Zum Beispiel benötigen wir weder R <83.617.563.821.029.283.746 noch R <2^1.000,001 usw.

So kann unser Modell die Anzahl der Register "erweitern", falls erforderlich, um eine bestimmte Berechnung durchzuführen. Jedoch das tut bedeuten, dass die Zahl, auf die das Modell erweitert wird, sein muss endlich- Es muss mit einer natürlichen Zahl indexierbar sein: ω ist keine Option.

Wir können dieser Einschränkung entgehen, indem wir ein unbegrenztes Register bereitstellen, um die Adresse des Registers anzugeben, das eine indirekte Adresse festlegt.

Siehe auch

Externe Links

Verweise

Mit wenigen Ausnahmen sind diese Referenzen die gleichen wie die bei Registrieren Sie Maschine.

- Goldstine, Herman H. und von Neumann, John, "Planung und Kodierung der Probleme für ein elektronisches Computerinstrument", Rep. 1947,, Institut für fortgeschrittenes Studium, Princeton. Nachdruck auf S. 92–119 in Bell, C. Gordon und Newell, Allen (1971), Computerstrukturen: Lesungen und Beispiele, McGraw-Hill Book Company, New York. ISBN0-07-004357-4}.
George Boolos, John P. Burgess, Richard Jeffrey (2002), Berechnbarkeit und Logik: vierte Ausgabe, Cambridge University Press, Cambridge, England. Der ursprüngliche Boolos-Jeffrey-Text wurde von Burgess ausgiebig überarbeitet: Fortgeschrittener als ein einführendes Lehrbuch. Das Modell "Abacus Machine" wird in Kapitel 5 ausführlich entwickelt Abacus -Berechnbarkeit; Es ist eines von drei Modellen, die ausgiebig behandelt und verglichen wurden-die Turing-Maschine (immer noch in Boolos 'ursprünglicher 4-Tupel-Form) und die anderen beiden Rekursion.
Arthur Burks, Herman Goldstine, John von Neumann (1946), Vorläufige Diskussion über das logische Design eines elektronischen Computerinstruments, nachgedruckt S. 92ff in Gordon Bell und Allen Newell (1971), Computerstrukturen: Lesungen und Beispiele, McGraw-Hill Book Company, New York. ISBN0-07-004357-4.
Stephen A. Cook und Robert A. Reckhow (1973), Zeitverletzte Zufallszugriffsmaschinen, Journal of Computer Systems Science 7 (4): 354-375.
Martin Davis (1958), Berechnbarkeit und Unlöslichkeit, McGraw-Hill Book Company, Inc. New York.
Calvin Elgot und Abraham Robinson (1964), Random-Access gespeicherte Produktmaschinen, ein Ansatz für Programmiersprachen, Journal of the Association for Computing Machinery, Vol. 11, Nr. 4 (Oktober 1964), S. 365–399.
J. Hartmanis (1971), "Computational Complexity of Random Access gespeicherte Programmmaschinen", Mathematical Systems Theory 5, 3 (1971), S. 232–245.
John Hopcroft, Jeffrey Ullman (1979). Einführung in die Automatentheorie, Sprachen und Berechnungen, 1. Aufl., Reading Messe: Addison-Wesley. ISBN0-201-02988-x. Ein schwieriges Buch, das sich auf die Fragen der maschinellen Interpretation von "Sprachen", NP-Completness usw. konzentriert, etc.
Stephen Kleene (1952), Einführung in Metamathematik, North-Holland Publishing Company, Amsterdam, Niederlande. ISBN0-7204-2103-9.
Donald Knuth (1968), Die Kunst der Computerprogrammierung, Zweite Ausgabe 1973, Addison-Wesley, Reading, Massachusetts. Vgl. Seiten 462-463, wo er "eine neue Art von abstrakter Maschine oder" Automat "definiert, die sich mit verknüpften Strukturen befasst.
Joachim Lambek (1961, erhalten am 15. Juni 1961), So programmieren Sie einen unendlichen Abakus, Mathematical Bulletin, Vol. 4, nein. 3. September 1961 Seiten 295-302. In seinem Anhang II schlägt Lambek eine "formale Definition des Programms" vor. Er bezieht sich auf Melzak (1961) und Kleene (1952). Einführung in Metamathematik.
Z. A. Melzak (1961, erhalten am 15. Mai 1961), Ein informeller arithmetischer Ansatz zur Berechnung und Berechnung, Kanadisches mathematisches Bulletin, vol. 4, nein. 3. September 1961 Seiten 279-293. Melzak bietet keine Referenzen an, erkennt jedoch "den Vorteil von Gesprächen mit Drs. R. Hamming, D. McIlroy und V. Vyssots von den Bell -Telefonlaborern und mit Dr. H. Wang von der Universität Oxford" an.
Marvin Minsky (1961). "Rekursive Unlöslichkeit von Posts Problem von 'Tag' und anderen Themen in Theorie der Turing -Maschinen". Annalen der Mathematik. Die Annals of Mathematics, Vol. 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, N. J.: Prentice-Hall, Inc. Insbesondere siehe Kapitel 11: Modelle ähnlich wie digitale Computer und Kapitel 14: Sehr einfache Grundlagen für die Berechnung. Im früheren Kapitel definiert er "Programmmaschinen" und erörtert im späteren Kapitel "Universal Program Machines mit zwei Registern" und "... mit einem Register" usw.
John C. Shepherdson und H. E. Sturgis (1961) erhalten Dezember 1961 Berechnung der rekursiven Funktionen, 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 andere unter Bezugnahme auf "Minimalität der in 4.1 verwendeten Anweisungen: Vergleich mit ähnlichen Systemen".

Kaphengst, Heinz, Ein Abstrakte Programmgesteuerte Rechenmaschine ', Zeitschrift Fur Mathematische Logik und Grundlagen der Mathematik:5 (1959), 366-379.
Ershov, A. P. P. Auf 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, Dialektica 12 (1958), 373.
Hermes, Hans Die Universalität programmgesteuerter revhenmaschinen. Math.-Phys. Semsterberichter (Göttingen) 4 (1954), 42-53.

Arnold Schönhage (1980), Speichermodifikationsmaschinen, Gesellschaft für industrielle und angewandte Mathematik, Siam J. Comput. Vol. 9, No. Speichermodifikationsmaschinen, in Theoretische Informatik (1979), S. 36–37
Peter van Emde Boas, "Maschinenmodelle und Simulationen" S. 3–66, in: Jan van Leeuwen, ed. Handbuch der theoretischen Informatik. Band A: Algorithmen und Komplexität, The MIT Press/Elsevier, 1990. ISBN0-444-88071-2 (Band A). QA 76.H279 1990. Van Emde Boass Behandlung von SMMs erscheint auf S. 32–35. Diese Behandlung verdeutlicht Schōnhage 1980 - sie folgt genau, erweitert aber leicht die Schōnhage -Behandlung. Beide Referenzen können für ein effektives Verständnis erforderlich sein.
Hao Wang (1957), Eine Variante zu Turings Theorie der Computermaschinen, JACM (Journal of the Association for Computing Machinery) 4; 63-92. Präsentiert auf der Sitzung des Vereins vom 23. bis 25. Juni 1954.