Registermaschine

Die Registermaschine (RM) ist eine abstrakte Maschine der theoretischen Informatik. Registermaschinen sind Turing-vollständig, das heißt, sie sind prinzipiell zu allen Berechnungen in der Lage, die Turingmaschinen oder auch reale Rechner ausführen können. Da man beweisen kann, dass sich die Registermaschine und die Turingmaschine gegenseitig mit polynomieller Laufzeit simulieren können, gelten Aussagen, die man für die Turingmaschine beweisen kann, auch für die Registermaschine und damit auch für jede beliebige Rechenmaschine. Dies ist in der theoretischen Informatik von Vorteil, da man viele Aussagen anhand der Turingmaschine leichter beweisen kann.

Geschichte

Das Modell geht auf eine Arbeit von John C. Shepherdson und Howard E. Sturgis (* 1936) aus dem Jahr 1963 zurück, wobei diese einen Vorläufer in Heinz Kaphengst hatten.

Formale Definition

Es gibt verschiedene, leicht voneinander abweichende Definitionen von Registermaschinen. Je nach Autor unterscheiden sich die Befehle und deren Bedeutung. Im Folgenden wird eine einfache Registermaschine mit drei Grundoperationen beschrieben.

Die Registermaschine arbeitet mit natürlichen Zahlen. Alle ab jetzt vorkommenden Zahlen sollten in diesem Kontext betrachtet werden.

Die Registermaschine besteht aus:

• einem Programm bestehend aus endlich vielen durchnummerierten Befehlen (beginnend mit Nummer 1)
• einem Befehlszähler b
• einem Input-Wert m
• einem Output-Wert n
• und aus einem unendlich großen Speicher aus durchnummerierten Speicherzellen (Register) r(1), r(2), r(3), ... Jedes Register speichert eine natürliche Zahl.

Ein Programm setzt sich aus folgenden Befehlen zusammen:

Befehl	Wirkung 1	Wirkung 2	Erklärung
$A_{i}$ then p	r(i) := r(i) + 1	b := p	Inkrementieren eines Registers um 1.
$S_{i}$ then p	Wenn r(i) > 0 dann r(i) := r(i) - 1	b := p	Dekrementieren eines Registers um 1, falls der Inhalt des Registers nicht bereits 0 ist.
if $T_{i}$ then p else q		Wenn r(i) = 0 dann b := p ansonsten b := q	Testen, ob ein Register 0 enthält.

Zum Starten des Programms sollte zusätzlich ein Eingabedatensatz bestehend aus m geordneten Werten vorhanden sein.

Zu Beginn wird der Befehlszeiger b auf den Wert der Startmarke des Programms gesetzt. Die Speicherzellen von Nummer 1 bis m werden auf die entsprechenden Werte des Eingabedatensatzes gesetzt. Die restlichen Speicherzellen erhalten den Wert 0.

Die Registermaschine führt dann nacheinander die Befehle des Programms aus. Es wird immer der Befehl mit der Nummer b ausgeführt. Die Ausführung eines nichtexistenten Befehls terminiert das Programm.

Nach der Terminierung werden alle Werte von r(1) bis r(n) ausgegeben.

Registermaschinen lassen sich wie alle Maschinen anschaulich besonders gut durch Flussdiagramme darstellen.

Beispiel Identitätsfunktion

Beispiel für eine Registermaschine

Die rechts abgebildete Registermaschine gibt immer den Wert aus, der ihr als erster Eingabewert übergeben wird.

Das blau unterlegte Kästchen des Flussdiagramms stellt einen Test dar. Fällt dieser negativ aus, so läuft die Registermaschine durch die Schleife und dekrementiert bei jedem Schleifendurchlauf $R_{1}$ und inkrementiert $R_{0}$. Schließlich enthält $R_{1}$ den Wert 0, der Test fällt positiv aus und die Maschine geht in den Haltezustand über. Es ist klar, dass im Haltezustand immer genau der Eingabewert aus $R_{1}$ in $R_{0}$ stehen muss. Die vorliegende Registermaschine ist also eine einfache Implementierung der Identitätsfunktion.

Random Access Machine

Die Random Access Machine (kurz RAM) ist eine spezielle Art von Registermaschine. Sie hat die Fähigkeit der indirekten Adressierung der Register.

Die Random Access Machine besteht aus:

• einem Programm bestehend aus endlich vielen durchnummerierten Befehlen (beginnend mit Nummer 1)
• einem Befehlszähler b
• einem Akkumulator c(0)
• und einem unendlich großen Speicher aus durchnummerierten Speicherzellen (Registern) c(1), c(2), c(3), …

Jedes Register (einschließlich b und c(0)) speichert eine beliebig große natürliche Zahl.

Zu Beginn enthält der Befehlszähler b den Wert 1, der Akkumulator den Wert 0. Die Speicherzellen ab Nummer 1 enthalten zu Beginn die endliche Eingabe. Die restlichen Speicherzellen enthalten den Wert 0.

Ein Programm setzt sich aus folgenden Befehlen zusammen:

Befehl	Wirkung 1	Wirkung 2
LOAD i	c(0):=c(i)	b:=b+1
CLOAD i	c(0):=i	b:=b+1
INDLOAD i	c(0):=c(c(i))	b:=b+1
STORE i	c(i):=c(0)	b:=b+1
INDSTORE i	c(c(i)):=c(0)	b:=b+1
ADD i	c(0):=c(0)+c(i)	b:=b+1
CADD i	c(0):=c(0)+i	b:=b+1
INDADD i	c(0):=c(0)+c(c(i))	b:=b+1
SUB i	$c(0):=\max(c(0)-c(i),0)$	b:=b+1
CSUB i	$c(0):=\max(c(0)-i,0)$	b:=b+1
INDSUB i	$c(0):=\max(c(0)-c(c(i)),0)$	b:=b+1
MUL i	c(0):=c(0)*c(i)	b:=b+1
CMUL i	c(0):=c(0)*i	b:=b+1
INDMUL i	c(0):=c(0)*c(c(i))	b:=b+1
DIV i	$c(0):=\lfloor c(0)/c(i)\rfloor$	b:=b+1
CDIV i	$c(0):=\lfloor c(0)/i\rfloor$	b:=b+1
INDDIV i	$c(0):=\lfloor c(0)/c(c(i))\rfloor$	b:=b+1
GOTO i		b:=i
IF c(0) $\alpha \,l$ GOTO i $\alpha \in \{<,=,\neq ,>\},\;l\in \mathbb {N}$		b:=i falls Bedingung wahr, b:=b+1 sonst.
END		b:=b

Die Registermaschine führt nacheinander die Befehle des Programms aus. Es wird immer der Befehl mit der Nummer b als Nächstes ausgeführt. Fast alle Befehle erhöhen den Befehlszähler um 1, so dass nach einem solchen Befehl der darauf folgende Befehl, mit der nächsthöheren Nummer, ausgeführt wird. Die Registermaschine hält an, sobald der Befehlszähler b den Befehl END bezeichnet. Das Ergebnis der Berechnung steht dann in (zuvor) definierten Registern.

Siehe auch

• Verfeinerung (Informatik)
• Kellerautomat
• Akkumulatorrechner
• Wahlfreier Zugriff
• Berechenbarkeitstheorie

Literatur

• John C. Shepherdson, Howard E. Sturgis: Computability of Recursive Functions. In: Journal of the Association of Computing Machinery (JACM). Bd. 10, Nr. 2, 1963, ISSN 0004-5411, S. 217–255 doi:10.1145/321160.321170 (eingegangen Dezember 1961).

Weblinks

• Registermaschine, Hessischer Bildungsserver
• Registermaschine (RAM), Church-Turing-These, Prof. Dr. Berthold Vocking, RWTH Aachen, 2010 (PDF)
• Vorlesung Theoretische Informatik II, Bernhard Beckert, Universität Koblenz Landau, 2007 (PDF)