Registermaschine
In der Literatur werden verschiedene Varianten von Registermaschinen beschrieben. Im Hinblick auf das Landesabitur ist deshalb ein einheitliches Modell erforderlich, das als Grundlage für Abituraufgaben verwendet wird. Dieses Modell orientiert sich am Buch Theoretische Informatik von A. Asteroth und C. Baier, weist aber einige Unterschiede auf.
Eine Registermaschine besteht aus unendlichen vielen Registern R1, R2, R3,..., in denen natürliche Zahlen gespeichert werden. Sie verfügt zusätzlich über einen Akkumulator, der das Ergebnis des jeweils letzten Rechen- oder Ladebefehls enthält. Die Arbeitsweise wird durch ein Programm angegeben. Dieses setzt sich aus einer Folge von einzelnen Befehlen zusammen, die zeilenweise untereinander geschrieben werden. Programmzeilen kann man mit einer Marke versehen, um Sprünge dorthin ausführen zu können.
Die Registermaschine hat die Befehle: LOAD, STORE, ADD, SUB, MUL, DIV, GOTO, JZERO, JNZERO und END. Bei den Sprungbefehlen wird als Operand eine Marke angegeben. Bei den arithmetischen Befehlen und den Speicherbefehlen sind drei Arten von Operanden zulässig:
| Operand | Bedeutung | Beispiel | |
| Konstanten | #i | der Operand ist die Zahl i | LOAD #7 |
| direkte Adressierung | i | der Operand ist das Register i | ADD 4 |
| indirekte Adressierung | *i | der Operand ist das Register, dessen Nummer im Register i steht |
STORE *3 |
In der folgenden Befehlsübersicht bedeutet x den jeweiligen Operanden:
| Befehl | Bedeutung |
| LOAD x | Lädt x in den Akkumulator |
| STORE x | Speichert den Inhalt des Akkumulators in x. Dabei darf x keine Konstante #i sein. |
| ADD x | Addiert x zum Akkumulator |
| SUB x | Subtrahiert x vom Akkumulator. Ist der Wert von x größer als der des Akkumulators, ist das Ergebnis 0. |
| MUL x | Multipliziert x mit dem Akkumulator. |
| DIV x | Dividert den Akkumulatorinhalt durch x. Für x = 0 wird das Programm beendet. |
| GOTO M | Ein unbedingter Sprung zur Marke M. |
| JZERO M | Falls der Akkumulator den Wert 0 hat, erfolgt ein Sprung zur Marke M. |
| JNZERO M | Falls der Akkumulator einen Wert größer 0 hat, erfolgt ein Sprung zur Marke M. |
| END | Das Programm wird beendet. |
Beispiel 1: Registermaschine für die Berechnung von nm.
Registerbelegung
| R1 | n |
| R2 | m |
| R3 | Ergebnis |
Programm
| LOAD #1 | // Initialisierung mit Ergebnis = 1 | |
| STORE 3 | ||
| M1: | LOAD 2 | // lade Exponent |
| JZERO Ende | // m = 0, Berechnung fertig | |
| SUB #1 | // m = m - 1 | |
| STORE 2 | ||
| LOAD 3 | ||
| MUL 1 | // Ergebnis = Ergebnis * n | |
| STORE 3 | ||
| GOTO M1 | // nächster Schleifendurchlauf | |
| Ende: | END |
Beispiel 2: Registermaschine als Akzeptor für anbn.
Diese Registermaschine akzeptiert die Sprache L = { anbn | n ∈ Ν }. Sie erhält ein Wort w über dem Alphabet E = {a, b} als Eingabe und entscheidet, ob es die Form anbn hat. Das erste Zeichen von w wird im ASCII-Code im Register R4 gespeichert, alle weiteren in den darauffolgenden Registern. a hat den ASCII-Code 141 und b die 142.
Registerbelegung
| R1 | Eingabeposition, Anfangswert 4 |
| R2 | Anzahl a - Anzahl b |
| R3 | Ausgabe 1 für akzeptiert, 0 für nicht akzeptiert |
| R4... | das Eingabewort |
Programm
| LOAD #4 | // R1 initialisieren | |
| STORE 1 | ||
| LOAD #0 | // R2 und R3 initialisieren | |
| STORE 2 | ||
| STORE 3 | ||
| AZählen: | LOAD *1 | |
| JZERO Fertig | // Ende der Eingabe | |
| SUB #141 | ||
| JNZERO BZählen | // kein a mehr | |
| LOAD 2 | ||
| ADD #1 | ||
| STORE 2 | ||
| LOAD 1 | // nächstes Zeichen | |
| ADD #1 | ||
| STORE 1 | ||
| GOTO AZählen | ||
| BZählen: | LOAD *1 | |
| JZERO Fertig | // Ende der Eingabe | |
| SUB #141 | ||
| JZERO Ende | // ein a nach einem b | |
| LOAD 2 | ||
| JZERO Ende | // mehr b als a | |
| SUB #1 | ||
| STORE 2 | ||
| LOAD 1 | // nächstes Zeichen | |
| ADD #1 | ||
| STORE 1 | ||
| GOTO BZählen | ||
| Fertig: | LOAD 2 | |
| JNZERO Ende | ||
| LOAD #1 | ||
| STORE 3 | ||
| Ende: | END |
Simulationsprogramme
Herr Norman Sutatyo hat das Simulationsprogramm remasp (Version 3.6 vom 7.12.2022) geschrieben, mit dem Registermaschinenprogramme schrittweise ausgeführt werden können.
Der Sourcecode steht unter https://github.com/groehner/Remasp zur Verfügung.
Der LK-Schüler Eric Schäfer der Lichtenbergschule Darmstadt hat ein Simulationsprogramm in JavaScript geschrieben, das daher ohne Download und Installation direkt im Browser aufgerufen werden kann: https://ericdoes.codes/Abitur/Register/