Registermaschine/Programmbeispiele/Animationen/Textabschnitt

Auf dieser Seite werden mehrere Registermaschinen mit Animationen und Erläuterungen vorgestellt. Die Animationen umfassen Registermaschinen aus Übungen, Teilprogramme für größere Registermaschinen und komplexere Registermaschinen.

Erläuterung der Farben

Gelb: Zeigt den aktuellen Befehl an.
Schwaches Gelb: Zeigt aktuelle und folgende Befehlszeile nach einem Sprungbefehl an.
Blau: Testet das Register, ob Inhalt = $0$ ist.
Schwaches Grün: Der Inhalt des Registers = $0$ und es wird gesprungen.
Schwaches Rot: Der Inhalt des Registers ≠ $0$ und es wird nicht gesprungen.
Grün: Der Inhalt des Registers wird erhöht.
Rot: Der Inhalt des Registers wird verringert.

Bei manchen Animationen wird auf Zwischenschritte verzichtet, um das Programm schneller ablaufen zu lassen.

Sechszeilige Registermaschinen

RM mit einem Druckbefehl

RM mit einem Sprungbefehl

RM die abwechselnd 1 und 0 ausdrucken

Die Registermaschine besteht aus 6 Befehlszeilen und druckt bei leerer Startbelegung abwechselnd $1$ und $0$ . Die Registermaschine kommt dabei mit einem Druckbefehl aus und hält nicht an.

Die Registermaschine besteht aus 6 Befehlszeilen und druckt bei leerer Startbelegung abwechselnd $1$ und $0$ . Die Registermaschine kommt dabei mit einem Sprungbefehl aus und hält nicht an. Das zweite Register wäre nicht nötig, weil Register $1$ beim Sprung immer $0$ ist.

Bis 100 zählen

Die Aufgabe der Registermaschine ist es, bei leerer Startbelegung bis $100$ zu zählen und dann anzuhalten. Das Ziel war es, dass die Registermaschine dabei mit möglichst wenigen Befehlszeilen auskommt.

Die Registermaschine besteht aus zwei verschachtelten Schleifen und nutzt die Tatsache, dass $100$ das Produkt aus $4 * 5 * 5$ ist.

1. bis 4. Mit den ersten $4$ Zeilen wird Register $3$ auf $4$ erhöht. Die Abbruchbedingung der äußeren Schleife ist in Zeile $27$ und bezieht sich auf Register $3$ . Insgesamt wird diese Schleife deshalb viermal durchlaufen und macht die äußere Schleife somit zum Faktor $4$ für das Produkt.

5. bis 19. Die äußere Schleife wird insgesamt viermal durchlaufen, weil der Inhalt von Register $3$ beim ersten Eintritt in die Schleife bei $4$ ist.

9. bis 16. Die innere Schleife erhöht den Inhalt von Register $1$ jedesmal um $5$ . Die Abbruchbedingung ist in Zeile $14$ und bezieht sich auf Register $2$ . Da die Schleife zunächst durchläuft und erst am Ende auf Register $2$ geprüft wird, wird Register $1$ insgesamt fünfmal (viermal wegen dem Inhalt von Register $2$ und ein zusätzliches Mal, weil die Prüfung erst nach einem Durchlauf kommt). Ein kompletter Durchlauf der inneren Schleife erhöht den Inhalt von Register $1$ um $25$ (Die Schleife wird fünfmal durchlaufen und erhöht den Inhalt von Register $1$ wegen der Zeilen $9$ bis $13$ jedesmal um $5$ .

Zum Schluss sind Register $2$ und $3$ leer. Dadurch wird in Zeile $18$ zum Haltebefehl gesprungen und die Registermaschine hält an.

Hilfsprogramme

Die nachfolgenden Registermaschinen sind Hilfsprogramme zum Rechnen für größere Registermaschinen. Sie sollen zeigen, dass man mit Registern komplexere Rechenoperationen durchführen kann. Der Aufbau ist dabei immer der gleiche. Statt in Befehlszeile $B_{m}$ die Abkürzung zu verwenden, beispielsweise Leere Register $R_{i}$ springt die Registermaschine an eine Stelle, die für den Verlauf anderer Prozesse irrelevant ist, berechnet die Vorgabe mithilfe der Grundbefehle oder solcher, bei denen bereits gezeigt wurde, dass man sie mit Grundbefehlen darstellen kann, und springt am Ende in die Zeile $B_{m + 1}$ zurück, sodass das ursprüngliche Programm an der Stelle weiterlaufen kann. Mit den Registern $R_{i}$ und $R_{j}$ wird gerechnet. Das Register $R_{l}$ bleibt immer leer und dient somit als Bedingung für einen Sprungbefehl. Register $R_{h}$ ist ein Hilfsregister, dass für das Teilprogramm benötigt wird oder das Ergebnis speichert. Alle weiteren Register, die in den Teilprogrammen vorkommen, werden für die Rechenoperationen gebraucht. Es wurde darauf geachtet, dass diese am Ende der Berechnungen wieder leer sind, sodass man das Teilprogramm erneut nutzen kann, also die Startbelegung wieder hergestellt wurde.

Leere Register

Das Programm ist sehr einfach. $R_{i}$ wird schrittweise mit geleert. Bei jedem Schritt wird geprüft, ob $R_{i}$ bereits leer ist, wenn das der Fall ist, springt der Teilabschnitt wieder ins Hauptprogramm. Falls nicht, wird der Vorgang wiederholt. Das passiert solange, bis der Inhalt von $R_{i}$ irgendwann $0$ ist.

Verschiebe Inhalt

Der Inhalt von $R_{i}$ soll zum Inhalt von $R_{j}$ addiert werden, sodass am Ende die Summe von $R_{i}$ und $R_{j}$ in $R_{j}$ steht und $R_{i}$ sich leert. Wenn $R_{j}$ zu Beginn leer war, wird praktisch nur der Inhalt von einem Register in ein anderes verschoben. Dazu wird schrittweise der Inhalt von $R_{i}$ geleert und gleichzeitig der von $R_{j}$ erhöht.

Addiere Register

Im Gegensatz zum Teilabschnitt, der den Inhalt verschiebt, wird der Inhalt von $R_{i}$ dabei nicht verändert. Dazu wird vorher der Inhalt von $R_{i}$ kopiert und anschließend der Inhalt des kopierten Registers zum Verschieben benutzt. So bleibt der Inhalt von $R_{i}$ gleich und die Summe von $R_{i}$ und $R_{j}$ steht im $R_{j}$ . Andere beteiligte Register bleiben am Ende leer.

Kopiere Register

Das Ziel der Registermaschine ist es, den Inhalt von $R_{i}$ in $R_{j}$ zu kopieren, ohne dabei den Inhalt von $R_{i}$ zu verändern. Dazu wird das Hilfsregister $R_{h}$ benötigt. Zunächst leert man schrittweise das $R_{i}$ und erhöht dabei gleichzeitig $R_{j}$ und $R_{h}$ . Am Ende ist $R_{i}$ leer und der ursprüngliche Wert von $R_{i}$ ist jetzt in $R_{j}$ und $R_{h}$ . Da man aber $R_{i}$ für den Ablauf des Hauptprogrammes nicht verändern möchte, wird zum Schluss $R_{h}$ geleert und dabei $R_{i}$ erhöht, sodass der Inhalt von $R_{h}$ zu $R_{i}$ verschoben wird. Zum Schluss hat $R_{i}$ seinen ursprünglichen Wert und $R_{h}$ ist wie zu Beginn leer. Und, wie gewünscht, ist der Inhalt von $R_{i}$ nach $R_{j}$ kopiert worden. Im Gegensatz zum Verschieben wird der Inhalt von $R_{i}$ nicht geändert.

Multipliziere Register

Die Multiplikation ist eine wiederholte Addition. Eine Schleife sorgt bei jedem Schritt, dass der Inhalt von $R_{i}$ auf den Inhalt von $R_{h}$ addiert wird. Der Schleifenzähler ist der Inhalt von $R_{j}$ . Um die Inhalte von $R_{j}$ unberührt zu lassen, wird zu Beginn $R_{j}$ kopiert und die Kopie ist der eigentliche Schleifenzähler. Da das Produkt zweier Zahlen immer $0$ ist, wenn ein Faktor $0$ ist, wird zuallererst getestet, ob $R_{i}$ oder $R_{j}$ $0$ sind, bevor das eigentliche Teilprogramm beginnt.

Potenziere Register

Ähnlich wie die Registermaschine zur Berechnung eines Produkts. Eine Potenz ist eine Wiederholung von Multiplikationen. Das Programm sieht nur deshalb komplizierter aus, weil mehr Fälle zu betrachten sind, die unterschiedlich behandelt werden müssen. Bei der Multiplikation hat es ausgereicht zu prüfen, ob eines der beiden Register leer ist, weil dann das Produkt sofort klar ist. Bei der Berechnung einer Potenz gibt es jedoch vier Fälle, die betrachtet werden müssen. Register $R_{i}$ ist dabei die Basis und $R_{j}$ der Exponent. Das Ergebnis steht am Ende in Register $R_{h}$ .

Fall 1: Exponent und Basis sind beide $0$ . $0^{0}$ ist nicht definiert, darum hält das Programm an dieser Stelle an. Man könnte sich auch entscheiden, in eine Endlosschleife zu gehen, sodass das Programm nicht anhält. Eine dritte Option wäre es, ein leeres Register, dass sonst nicht im Programmablauf vorkommt, um $1$ zu erhöhen und dann anzuhalten. Dieses Register wäre dafür da, zu signalisieren, warum die Registermaschine angehalten hat, quasi als Fehlermeldung.

Fall 2: Nur die Basis ist $0$ . $0$ mit sich selbst zu multiplizieren ergibt immer $0$ . Das Ergebnis ist als immer $0$ . Diese Zahl steht bereits in $R_{h}$ . Man kann also direkt nach dem Test von $R_{j}$ (dass ≠ $0$ ist) zurück ins Hauptprogramm gehen.

Fall 3: Nur der Exponent ist $0$ . Wenn der Exponent $0$ ist, dann ist das Ergebnis immer gleich $1$ . Darum wird für diesen Fall $R_{h}$ um $1$ erhöht, bevor zurück zum Hauptprogramm gesprungen wird.

Fall 4: Exponent und Basis sind von $0$ verschieden. Erst nachdem die oben drei Fälle ausgeschlossen wurden, kann man wirklich die Potenz berechnen. Ähnlich wie bei der Multiplikation wird hier $R_{i}$ zum Ergebnis multipliziert, bis die Abbruchbedingung eintritt. Diese ist von $R_{j}$ abhängig, dass zu Beginn jedoch kopiert wird. Die Kopie wird bei jedem Schleifendurchlauf um $1$ reduziert, bis schließlich die Potenz vollständig berechnet wurde und das Teilprogramm zum Hauptprogramm zurückspringt.

Fall 1: Exponent und Basis sind 0

Fall 2: Nur die Basis ist 0

Fall 3: Nur der Exponent ist 0

Fall 4: Exponent und Basis sind von 0 verschieden

Fallunterscheidungen beim Potenzieren.

Collatz-Algorithmus

Der Collatz-Algorithmus besteht im wesentlichen aus einer Fallunterscheidung. Bei einer geraden Zahl wird die Zahl halbiert. Bei einer ungeraden Zahl wird sie mit $3$ multipliziert und dann wird $1$ hinzuaddiert. Wenn die Zahl $1$ ist, hält die Maschine an. Im ersten Register steht zu Beginn eine beliebige Zahl, dann fängt der Algorithmus an. Jedes Zwischenergebnis wird ausgedruckt. Wenn das Zwischenergebnis $1$ ist, hält die Maschine an. In jedem anderen Fall läuft die Registermaschine weiter.

Erklärung des Programmablaufs:

1. Der Inhalt von $R_{1}$ wird ausgedruckt. Diese Zeile wird nur zu Beginn einmal durchlaufen und dient dazu, bei dem Ausdruck am Ende nachzuvollziehen, mit welcher Zahl begonnen wurde.

2 - 4. Die Zeilen testen, ob der Inhalt von $R_{1}$ gleich $1$ ist. Wenn der Inhalt $1$ ist, hält das Programm an, wenn nicht, geht es weiter. Diese drei Zeilen werden nach jedem Schritt durchlaufen und sind die Abbruchbedingung der Schleifen. Für den Sonderfall, dass beim Start $R_{1}$ leer war, wird die Registermaschine beim ersten Betreten dieses Abschnitts beendet.

5 - 16. Diese Zeilen sind das Kernstück des Algorithmus. Es ist eine Schleife, die zwei Abbruchbedingungen in Zeile $10$ und $15$ hat. Die Schleife besitzt zwei Hälften. Die obere Hälfte geht von Zeile $5$ bis $10$ , die untere von $11$ bis $15$ . In jeder Hälfte wird $R_{1}$ um $1$ reduziert und am Ende getestet, ob $R_{1}$ jetzt leer ist. Wenn $R_{1}$ bei Eintritt in die Schleife ungerade war, dann wird irgendwann die Abbruchbedingung von Zeile $10$ erfüllt. Diese führt dann zu Zeile $17$ mit dem Wissen, die Zahl war ungerade. Andersherum gilt für den unteren Teil der Schleife, dass sie genau dann abbrechen wird, wenn der Inhalt von $R_{1}$ gerade war und das Programm dann zu Zeile $22$ geht. Die übrigen Zeilen dieses Abschnitts bereiten $R_{2}$ und $R_{3}$ vor. $R_{2}$ wird gebraucht, falls $R_{1}$ gerade war, und $R_{3}$ für den Fall, dass $R_{1}$ ungerade war. $R_{2}$ füllt sich halb so schnell wie sich $R_{1}$ leert (Zeile $5$ und $11$ reduzieren den Inhalt von $R_{1}$ , während Zeile $14$ $R_{2}$ nur einmal erhöht pro Schleifendurchlauf). Wenn $R_{1}$ in Zeile $15$ leer ist, ist $R_{2}$ halb so groß wie $R_{1}$ beim Schleifeneintritt war. $R_{3}$ wird sechsmal erhöht, wenn $R_{1}$ um $2$ reduziert wird. Dabei wird in der ersten Hälfte $R_{3}$ um $4$ erhöht und in der zweiten Hälfte nur um $2$ . Der Trick ist dabei, wenn $R_{1}$ ungerade war, dass $R_{3}$ , wenn die Abbruchbedingung in Zeile $10$ greift, dreimal so groß ist, wie $R_{1}$ war, $+ 1$ .

17 - 21. Die Zeilen bereiten die Register für die nächsten Schritt vor. Der Inhalt von $R_{3}$ wird nach $R_{1}$ verschoben und gleichzeitig werden $R_{2}$ und $R_{3}$ geleert. Da der Inhalt von $R_{3}$ immer größer als $R_{2}$ ist, ist $R_{2}$ leer, wenn die Abbruchbedingung in Zeile $20$ erfüllt ist.

22 - 28. Die Zeilen bereiten ebenfalls die Register für den nächsten Schritt vor. Der Inhalt von $R_{2}$ wird nach $R_{1}$ verschoben. Anschließend folgt eine Schleife, die $R_{3}$ leert.

29 - 30. In Zeile $29$ wird gesprungen, wenn die Register für den nächsten Schritt vorbereitet wurden. Das heißt, in $R_{1}$ ist die nächste Zahl zum Testen und die $R_{2}$ und $R_{3}$ wurden geleert. Der Sprung beginnt den nächsten Schritt.

31. Wird nur erreicht, wenn der Algorithmus zum Ende kommt, sprich, $R_{1}$ den Inhalt $1$ hat (bzw. wenn $R_{1}$ zu Beginn leer war).