Registermaschine

Grundidee und Bedeutung

Eine Registermaschine (RM) ist eine abstrakte Maschine der theoretischen Informatik. Sie verarbeitet natürliche Zahlen in durchnummerierten Speicherzellen, den Registern, nach einem endlichen Programm aus einfachen Befehlen.

Registermaschinen sind Turing-vollständig. Das bedeutet: Sie können prinzipiell alle Berechnungen ausführen, die auch eine Turingmaschine oder ein realer Rechner ausführen kann. Registermaschine und Turingmaschine können sich gegenseitig mit polynomieller Laufzeit simulieren. Deshalb gelten Aussagen, die für Turingmaschinen bewiesen werden, auch für Registermaschinen und damit für beliebige Rechenmaschinen. Für viele Beweise ist das Modell der Turingmaschine besonders günstig.

Aufbau und Ausführung

Es gibt leicht unterschiedliche Definitionen von Registermaschinen; hier besteht eine einfache RM aus einem Programm mit endlich vielen, ab 1 nummerierten Befehlen, einem Befehlszähler b, einem Input-Wert m, einem Output-Wert n und unendlich vielen Registern r(1), r(2), r(3), … . Jedes Register speichert eine natürliche Zahl.

Zum Start steht b auf der Startmarke des Programms. Die Register 1 bis m erhalten die geordneten Werte des Eingabedatensatzes, alle übrigen Register den Wert 0. Danach wird stets der Befehl mit der Nummer b ausgeführt. Verweist b auf einen nicht vorhandenen Befehl, terminiert das Programm. Anschließend werden die Werte r(1) bis r(n) ausgegeben.

Die drei Grundoperationen sind: Aᵢ then p setzt r(i) := r(i) + 1 und b := p. Sᵢ then p vermindert r(i) um 1, falls r(i) > 0 ist, und setzt danach b := p. if Tᵢ then p else q prüft r(i): Bei r(i) = 0 wird b := p gesetzt, sonst b := q. Flussdiagramme eignen sich zur anschaulichen Darstellung solcher Programme.

Beispiel: Identitätsfunktion

Das dargestellte Beispiel gibt stets den ersten Eingabewert aus und implementiert damit die Identitätsfunktion. Ein Test prüft dabei, ob R₁ den Wert 0 enthält.

Ist der Test negativ, wiederholt die Maschine eine Schleife: Sie dekrementiert R₁ und inkrementiert R₀. Sobald R₁ den Wert 0 enthält, ist der Test positiv und die Maschine hält an. Im Haltezustand steht in R₀ genau der ursprüngliche Eingabewert aus R₁.

Random Access Machine

Die Random Access Machine (RAM) ist eine spezielle Registermaschine mit indirekter Adressierung. Dabei kann ein Registerinhalt selbst die Nummer des Registers festlegen, auf das zugegriffen wird. Die RAM besitzt ein endliches, ab 1 nummeriertes Programm, den Befehlszähler b, den Akkumulator c(0) sowie die Register c(1), c(2), … . Auch b und c(0) speichern beliebig große natürliche Zahlen.

Zu Beginn gilt b = 1 und c(0) = 0. Die Register ab Nummer 1 enthalten die endliche Eingabe; alle weiteren Register sind 0. Der Akkumulator ist das zentrale Arbeitsregister. LOAD i lädt c(i) in c(0), CLOAD i lädt die Konstante i. INDLOAD i lädt c(c(i)) und verwendet damit indirekte Adressierung. STORE i speichert c(0) in c(i), INDSTORE i in c(c(i)).

Für Rechnungen gibt es ADD, SUB, MUL und DIV sowie Varianten mit Konstanten (CADD, CSUB, CMUL, CDIV) und indirekter Adresse (INDADD, INDSUB, INDMUL, INDDIV). Bei der Subtraktion wird nicht negativ gerechnet: SUB i setzt c(0) := max(c(0) − c(i), 0); entsprechend nutzen CSUB und INDSUB diese Begrenzung. Division verwendet den ganzzahligen Abrundungswert, etwa DIV i: c(0) := ⌊c(0)/c(i)⌋.

Fast alle dieser Befehle erhöhen b um 1. GOTO i setzt b direkt auf i. IF c(0) α l GOTO i mit α ∈ {<, =, ≠, >} und l ∈ ℕ springt zu i, wenn die Bedingung wahr ist; andernfalls wird b := b + 1. END lässt b unverändert. Die Maschine hält an, wenn b den Befehl END bezeichnet; das Ergebnis steht dann in zuvor festgelegten Registern.