Q3.5 · Registermaschine

Ein weiteres Modell ist nicht nötig, weil die Turingmaschine zu schwach wäre. Es ist sinnvoll, weil unterschiedliche Modelle unterschiedliche Seiten von Berechnung sichtbar machen.

Die Turingmaschine lenkt den Blick auf Band, Kopf, Lesen, Schreiben und Bewegen. Die Registermaschine lenkt den Blick auf Programmtext, Zahlregister, Akkumulator, Programmzähler und Sprunglogik. Beide Modelle fragen nach algorithmischer Berechnung, aber sie machen verschiedene Strukturen beobachtbar.

Eine Registermaschine besteht aus Registern R1, R2, R3, ..., die natürliche Zahlen enthalten, einem Akkumulator als zentralem Rechenregister, einem Programm aus nummerierten oder markierten Befehlszeilen und einer aktuellen Programmposition (Befehlszähler).

• Eingaben stehen zu Beginn in den ersten k Registern.
• Nicht genutzte Register enthalten anfangs 0.
• Die Maschine startet in einer Startkonfiguration und endet in einer Endkonfiguration.
• Das Ergebnis steht je nach Konvention in einem festgelegten Register (oft R1) oder im Akkumulator.

Der Anschluss an Q3.4 liegt in der Idee der Konfiguration. Bei der Turingmaschine bestand eine Konfiguration aus aktuellem Zustand, Bandinhalt und Kopfposition. Bei der Registermaschine verschiebt sich diese Sicht: Entscheidend sind Programmzähler, Akkumulator und Registerbelegung.

Damit wird nicht ein Bandzustand verfolgt, sondern die Wirkung eines Programms auf Zahlenspeicher. Der Programmtext bleibt unverändert; die Ausführung entsteht dadurch, dass Befehle den Akkumulator, Registerwerte und die nächste Befehlsposition verändern.

Operandenarten klären, worauf ein Befehl eigentlich zugreift: auf eine Zahl selbst, auf ein fest benanntes Register oder auf ein Register, dessen Adresse erst aus einem anderen Register gelesen wird.

Indirekte Adressierung ist besonders wichtig: Wenn in Register R3 der Wert 8 steht, bedeutet *3, dass Register R8 verwendet wird.

• #7 bedeutet: nutze den Wert 7 selbst.
• 4 bedeutet: nutze den Inhalt von R4.
• *3 bedeutet: lies erst R3; dessen Wert ist die Nummer des verwendeten Registers.
• Direkte Adressierung liest oder beschreibt immer ein fest benanntes Register.
• Indirekte Adressierung nutzt den Registerinhalt als Adresse auf ein weiteres Register.
• Das macht Speicherzugriffe flexibler, aber auch fehleranfälliger.

x steht je nach Schreibweise für eine Konstante, ein direkt adressiertes Register oder ein indirekt adressiertes Register. Beispiel: Bei ADD #1 ist die Syntax „ADD mit Konstantenoperand“, die Semantik ist „Akkumulator um 1 erhöhen“. Bei STORE 3 bedeutet die Syntax „STORE mit direkter Adressierung“, semantisch wird der Akkumulator in R3 gespeichert. STORE #i ist unzulässig, weil in eine Konstante nicht gespeichert werden kann.

Sprungbefehle sind dabei keine gewöhnlichen Rechenbefehle. Sie verändern die Ablaufstruktur, weil sie den Programmzähler nicht einfach zur nächsten Zeile weiterlaufen lassen.

Syntax	Semantik
LOAD x	Lädt den Wert von x in den Akkumulator.
STORE x	Speichert den Akkumulatorwert in x; x darf keine Konstante sein.
ADD x	Addiert den Wert von x zum Akkumulator.
SUB x	Subtrahiert den Wert von x; über den natürlichen Zahlen gilt abgeschnittene Subtraktion: wäre das Ergebnis negativ, wird 0 gesetzt.
MUL x	Multipliziert den Akkumulator mit dem Wert von x.
DIV x	Dividiert den Akkumulator durch den Wert von x; bei x = 0 endet das Programm.
GOTO M	Unbedingter Sprung zur Marke M; der Programmzähler wird auf die Zielmarke gesetzt statt zur nächsten Zeile weiterzugehen.
JZERO M	Sprung zu M, wenn der Akkumulator 0 ist; sonst normale Fortsetzung mit der nächsten Zeile.
JNZERO M	Sprung zu M, wenn der Akkumulator größer 0 ist; sonst normale Fortsetzung mit der nächsten Zeile.
END	Beendet das Programm.

• Rechenbefehle LOAD, ADD, SUB, MUL und DIV wirken auf den Akkumulator.
• STORE x schreibt aus dem Akkumulator in ein Register; STORE #i ist unzulässig.
• SUB arbeitet über den natürlichen Zahlen mit abgeschnittener Subtraktion auf 0.
• DIV x beendet bei Division durch 0.
• Sprungbefehle verändern die nächste auszuführende Zeile über den Programmzähler.

Ein Registermaschinenprogramm wird zeilenweise ausgeführt. Nach normalen Befehlen geht es zur nächsten Zeile, Sprungbefehle ändern die nächste auszuführende Zeile. Die Beispiele sind deshalb als kleine Lernprogression angelegt: erst lineare Rechnung, dann Sprunglogik, danach Terminierungsgrenzen.

Eine Funktion ist registermaschinen-berechenbar, wenn es ein Registermaschinenprogramm gibt, das für passende Eingaben die richtigen Ausgaben berechnet. Entscheidend ist dabei nicht nur, ob irgendein Programm technisch endet, sondern ob es die intendierte mathematische Funktion auf ihrem Definitionsbereich korrekt berechnet.

Für Division gilt als Funktionsbeispiel oft f(n,m)=n DIV m. Fachlich ist bei m=0 Vorsicht nötig: Die übliche Division über den natürlichen Zahlen ist dort nicht definiert. Nach hessischem Modell beendet DIV 0 das Programm.

Daraus folgt gerade nicht, dass die mathematische Funktion für m=0 total definiert wäre. Programmhältung und mathematische Definiertheit sind nicht dasselbe: Ein Programm kann technisch enden, obwohl die intendierte Funktion für diese Eingabe nicht definiert ist.

Werkzeugperspektive auf den Trace: Total berechenbar heißt, dass die Ausführungsspur für jede zulässige Eingabe endet. Partiell berechenbar heißt, dass die Spur nur für Eingaben des Definitionsbereichs enden muss; außerhalb kann sie unendlich weiterlaufen.

undefined-loop ergänzt die Beispielreihe um die Grenze der Diagnose: Die Ausführung läuft ohne END weiter, bis das Werkzeug aus Sicherheitsgründen bei einer Schrittgrenze (maxSteps) stoppt. Diese Grenze begrenzt nur die konkrete Simulation und löst das Halteproblem nicht allgemein.

• increment: lineare Ausführung und Zusammenspiel von LOAD, ADD, STORE, END.
• double: Rechnen mit Registerwerten am Beispiel 2n.
• max: Fallunterscheidung und Sprunglogik.
• loop-counter: Programmzähler, Marken, Rücksprung und Schleifenverhalten.
• undefined-loop: Nichtterminierung als Diagnosegrenze; maxSteps ist nur eine praktische Simulationsgrenze.

Formal lässt sich die bisherige Unterscheidung so sichern: Eine partielle k-stellige Funktion f über den natürlichen Zahlen heißt registermaschinen-berechenbar, wenn es eine Registermaschine gibt, die bei jeder Eingabe aus dem Definitionsbereich in R1 bis Rk nach endlicher Zeit mit dem richtigen Ergebnis hält. Ist der Definitionsbereich die ganze betrachtete Eingabemenge und hält das Programm dafür immer, spricht man vom totalen Fall.

• Eingabekonvention: R1, ..., Rk enthalten die Eingabewerte.
• Ausgabekonvention dieser Seite: Ergebnis steht in R1; der Akkumulator dient als Rechen- und Zwischenspeicher.
• Partieller Fall: Für Eingaben außerhalb des Definitionsbereichs ist kein korrektes Ergebnis gefordert; je nach Programm kann Nichtterminieren oder ein technischer Endzustand auftreten.

Q3.5 liefert mit der Registermaschine ein konkretes Modell maschinennaher Berechnung. WHILE-Programme beschreiben Berechnung in einem anderen Programmiermodell: Variablen werden verändert, Schleifen steuern die Wiederholung. Die Grundfrage bleibt dieselbe: Welche Funktionen sind algorithmisch berechenbar?

• WHILE-Berechenbarkeit beschreibt algorithmische Berechnung ebenfalls formal.
• Wie bei Registermaschinen gibt es terminierende und nicht terminierende Programme.
• Registermaschinen-, WHILE-, GOTO- und Turing-Berechenbarkeit führen im Kern auf denselben Berechenbarkeitsbegriff.

Registermaschinen helfen, Berechnung präzise und maschinennah zu modellieren. Sie heben die Grenzen der Berechenbarkeit aber nicht auf.

• Manche Programme halten nicht.
• Nicht jede mathematisch mögliche Funktion ist berechenbar.
• Halteproblem und Entscheidbarkeitsgrenzen bleiben bestehen.

Damit schließt sich der Q3-Bogen von formalen Sprachen über Automaten bis zu Berechenbarkeitsmodellen: Unterschiedliche Modelle machen unterschiedliche Aspekte sichtbar, führen aber auf denselben Grundbegriff algorithmischer Berechnung. Der nächste Schritt verschiebt die Frage von „Ist es berechenbar?“ zu „Wie aufwändig ist diese Berechnung?“