Zum Inhalt springen

Registermaschine/Programmbeispiele/Animationen/Textabschnitt

Aus Wikiversity

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 = ist.
Schwaches Grün: Der Inhalt des Registers = und es wird gesprungen.
Schwaches Rot: Der Inhalt des Registers ≠ 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 und . 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 und . Die Registermaschine kommt dabei mit einem Sprungbefehl aus und hält nicht an. Das zweite Register wäre nicht nötig, weil Register beim Sprung immer ist.

Bis 100 zählen

Die Aufgabe der Registermaschine ist es, bei leerer Startbelegung bis 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 das Produkt aus ist.

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

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

9. bis 16. Die innere Schleife erhöht den Inhalt von Register jedesmal um . Die Abbruchbedingung ist in Zeile und bezieht sich auf Register . Da die Schleife zunächst durchläuft und erst am Ende auf Register geprüft wird, wird Register insgesamt fünfmal (viermal wegen dem Inhalt von Register 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 um (Die Schleife wird fünfmal durchlaufen und erhöht den Inhalt von Register wegen der Zeilen bis jedesmal um .

Zum Schluss sind Register und leer. Dadurch wird in Zeile 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 die Abkürzung zu verwenden, beispielsweise Leere Register 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 zurück, sodass das ursprüngliche Programm an der Stelle weiterlaufen kann. Mit den Registern und wird gerechnet. Das Register bleibt immer leer und dient somit als Bedingung für einen Sprungbefehl. Register 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. wird schrittweise mit geleert. Bei jedem Schritt wird geprüft, ob 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 irgendwann ist.

Verschiebe Inhalt

Teilabschnitt einer Registermaschine zur Verschiebung eines Inhalts

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

Addiere Register

Teilabschnitt einer Registermaschine zur Addierung zweier Register

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

Kopiere Register

Registermaschine zum Kopieren eines Registers in ein anderes

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

Multipliziere Register

Registermaschine zur Berechnung des Produktes zweier Register

Die Multiplikation ist eine wiederholte Addition. Eine Schleife sorgt bei jedem Schritt, dass der Inhalt von auf den Inhalt von addiert wird. Der Schleifenzähler ist der Inhalt von . Um die Inhalte von unberührt zu lassen, wird zu Beginn kopiert und die Kopie ist der eigentliche Schleifenzähler. Da das Produkt zweier Zahlen immer ist, wenn ein Faktor ist, wird zuallererst getestet, ob oder 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 ist dabei die Basis und der Exponent. Das Ergebnis steht am Ende in Register .


Fall 1: Exponent und Basis sind beide . 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 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 . mit sich selbst zu multiplizieren ergibt immer . Das Ergebnis ist als immer . Diese Zahl steht bereits in . Man kann also direkt nach dem Test von (dass ≠ ist) zurück ins Hauptprogramm gehen.

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

Fall 4: Exponent und Basis sind von verschieden. Erst nachdem die oben drei Fälle ausgeschlossen wurden, kann man wirklich die Potenz berechnen. Ähnlich wie bei der Multiplikation wird hier zum Ergebnis multipliziert, bis die Abbruchbedingung eintritt. Diese ist von abhängig, dass zu Beginn jedoch kopiert wird. Die Kopie wird bei jedem Schleifendurchlauf um 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 multipliziert und dann wird hinzuaddiert. Wenn die Zahl 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 ist, hält die Maschine an. In jedem anderen Fall läuft die Registermaschine weiter.

Erklärung des Programmablaufs:

1. Der Inhalt von 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 gleich ist. Wenn der Inhalt 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 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 und hat. Die Schleife besitzt zwei Hälften. Die obere Hälfte geht von Zeile bis , die untere von bis . In jeder Hälfte wird um reduziert und am Ende getestet, ob jetzt leer ist. Wenn bei Eintritt in die Schleife ungerade war, dann wird irgendwann die Abbruchbedingung von Zeile erfüllt. Diese führt dann zu Zeile 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 gerade war und das Programm dann zu Zeile geht. Die übrigen Zeilen dieses Abschnitts bereiten und vor. wird gebraucht, falls gerade war, und für den Fall, dass ungerade war. füllt sich halb so schnell wie sich leert (Zeile und reduzieren den Inhalt von , während Zeile nur einmal erhöht pro Schleifendurchlauf). Wenn in Zeile leer ist, ist halb so groß wie beim Schleifeneintritt war. wird sechsmal erhöht, wenn um reduziert wird. Dabei wird in der ersten Hälfte um erhöht und in der zweiten Hälfte nur um . Der Trick ist dabei, wenn ungerade war, dass , wenn die Abbruchbedingung in Zeile greift, dreimal so groß ist, wie war, .

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

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

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

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