Registermaschine

Die Registermaschine (RAM – Random Access Machine) ist ein alternatives Berechnungsmodell, das näher an realen Computern orientiert ist als die Turingmaschine. Sie besteht aus:

• Programmspeicher: Enthält eine nummerierte Folge von Befehlen.
• Befehlszähler (BZ): Zeigt auf den aktüll auszuführenden Befehl.
• Akkumulator (c(0)): Spezialregister für Berechnungen (Ergebnis von Operationen).
• Register r1, r2, r3, ...: Nummerierte Speicherzellen, die jeweils eine natürliche Zahl enthalten. Initial sind alle Register 0.

Der Befehlssatz einer typischen Registermaschine:

• LOAD i: Lade den Wert von Register r_i in den Akkumulator. c(0) := c(i)
• STORE i: Speichere den Akkumulatorwert in Register r_i. c(i) := c(0)
• ADD i: Addiere den Wert von r_i zum Akkumulator. c(0) := c(0) + c(i)
• SUB i: Subtrahiere den Wert von r_i vom Akkumulator. c(0) := max(0, c(0) − c(i))
• MULT i: Multipliziere. c(0) := c(0) × c(i)
• DIV i: Ganzzahlige Division. c(0) := c(0) / c(i)
• LOAD# k: Lade die Konstante k in den Akkumulator. c(0) := k
• GOTO j: Springe zu Befehl Nr. j. BZ := j
• IF c(0) = 0 GOTO j: Bedingter Sprung. Wenn Akkumulator = 0, springe zu j.
• IF c(0) > 0 GOTO j: Bedingter Sprung. Wenn Akkumulator > 0, springe zu j.
• END: Programm beenden.

Eingabe: r1 = 5, r2 = 3. Berechne r1 + r2 und speichere in r3:

1: LOAD 1       // c(0) := 5
2: ADD 2        // c(0) := 5 + 3 = 8
3: STORE 3      // c(3) := 8
4: END

Eingabe: r1 = a, r2 = b. Berechne a × b in r3:

1: LOAD# 0      // c(0) := 0
2: STORE 3      // r3 := 0 (Ergebnis)
3: LOAD 2       // c(0) := b
4: IF c(0)=0 GOTO 9  // wenn b=0, fertig
5: LOAD 3       // c(0) := r3
6: ADD 1        // c(0) := r3 + a
7: STORE 3      // r3 := r3 + a
8: LOAD 2       // c(0) := b
9: SUB# 1       // c(0) := b - 1
10: STORE 2     // r2 := b - 1
11: GOTO 3      // wiederhole
12: END

Die Registermaschine und die Turingmaschine sind berechnungsäquivalent:

• Jede TM kann eine Registermaschine simulieren: Die Register werden auf dem Band kodiert.
• Jede Registermaschine kann eine TM simulieren: Das Band wird in Registern gespeichert.

Beide Modelle berechnen exakt die gleiche Klasse von Funktionen – die Turing-berechenbaren Funktionen. Dies unterstützt die Church-Turing-These.

• Nähe zur Praxis: Registermaschine ist näher an realen Computern (Register, Befehle). TM ist abstrakter.
• Speicher: RM hat wahlfreien Zugriff auf Register. TM muss das Band sequentiell durchlaufen.
• Komplexitätsanalyse: RM wird häufig für Laufzeitanalysen verwendet (O-Notation). TM wird für Berechenbarkeitsfragen verwendet.
• Berechnungsstärke: Gleich – beide berechnen exakt die Turing-berechenbaren Funktionen.

Abitur-Tipp: Im Abitur wird häufig ein Registermaschinen-Programm gegeben, das Schritt für Schritt nachvollzogen werden soll (Tabelle mit BZ, c(0), r1, r2, ...). Übe das sorgfältige Protokollieren jedes Schritts. Typische Programme: Addition, Multiplikation durch wiederholte Addition, bedingte Verzweigungen. Die Äquivalenz zur TM ist ein beliebtes Verständnisthema.