Registermaschine/Programmbeispiele/Textabschnitt

Wir beschreiben einige Programme bzw. Programmabschnitte für Registermaschinen. Wenn man Programme aus schon entwickelten Programmabschnitten zusammensetzt, so ändern sich natürlich die absoluten Befehlsnummern im Programm, was wir aber ignorieren werden.

Beispiel

Einen unbedingten Sprung (ein „Go to-Befehl“) zu einer bestimmten Programmzeile, der also nicht von einer Abfrage abhängt, kann man dadurch realisieren, dass man ein neues Register ${}R_{k}$ hinzunimmt, das von keiner anderen Programmzeile adressiert wird und dessen Inhalt auf ${}0$ gesetzt wird. Dann bewirkt der Befehl ${}C(kj)$, dass zur ${}j$-ten Programmzeile gewechselt wird, da der Inhalt des Registers ${}R_{k}$ im gesamten Programmverlauf gleich ${}0$ bleibt.

Beispiel

Ein Programm soll sämtliche natürlichen Zahlen der Reihe nach ausdrucken. Dazu brauchen wir eine Registermaschine mit zwei Registern ${}R_{1}$ und ${}R_{2}$, die zum Start beide leer sind. Das zweite Register bleibt unverändert und wird nur für den unbedingten Sprungbefehl verwendet. Die Haltezeile wird nie erreicht.

1. Drucke
2. ${}1+$
3. Gehe zu ${}1$
4. Halte an

Beispiel

Das Register ${}R_{i}$ soll geleert werden. Dies geschieht durch das folgende Programm.

1. ${}C(i,4)$
2. ${}i-$
3. Gehe zu ${}1$
4. Halte an

Bemerkung  

Wir erlauben, dass bei einer Registermaschine die Anfangsbelegung der Register von außen festgelegt wird. Man könnte aber auch festlegen, dass die Anfangsbelegung stets die Nullbelegung ist, ohne die Berechnungsmöglichkeiten der Registermaschine einzuschränken. Dann kann man die eigentlich gewünschte Anfangsbelegung dadurch erreichen, dass man dem Programm ein „Belegungsprogramm“ voranstellt, das den einzelnen Registern ${}R_{i}$ durch die ${}s_{i}$ Befehle ${}i+,\ldots ,i+$ die gewünschte Belegung ${}s_{i}$ zuweist.

Man könnte auch erstmal ein „Entleerungsprogramm“ vorschalten, das alle Register leert und daran anschließend die Belegung durchführt, doch muss man für den Entleerungsvorgang, der nach Beispiel einen unbedingten Sprungbefehl verwendet, zumindest ein leeres Register zur Verfügung haben.

Wenn der Registerinhalt ${}r_{i}$ um eine natürliche Zahl ${}k$ erhöht werden soll, also ${}k$-fach direkt hintereinander inkrementiert werden soll, so schreiben wir dafür auch ${}i+\cdots +$ mit ${}k$ Pluszeichen.

Beispiel

Es soll mit einer Registermaschine festgestellt werden, ob der Inhalt ${}r_{i}$ des Registers ${}R_{i}$ größer oder gleich dem Inhalt ${}r_{j}$ des Registers ${}R_{j}$ ist. Dazu reserviert man das leere Register ${}R_{k}$ (${}i,j,k$ seien paarweise verschieden) und baut einen Programmabschnitt der folgenden Art.

1. ${}C(j,6)$
2. ${}j-$
3. ${}C(i,7)$
4. ${}i-$
5. Gehe zu ${}1$
6. ${}k+$
7. Halte an

Wenn dieser Programmabschnitt abgelaufen ist, so steht im Register ${}R_{k}$ der Wert ${}r_{k}=1$ oder ${}r_{k}=0$, je nachdem, ob ${}r_{i}\geq r_{j}$ ist oder nicht, und zwar unabhängig davon, ob man damit die Eingangsdaten oder Zwischendaten, wenn das Programm den ersten Befehl abarbeitet, meint. Die Korrektheit dieses Programms beruht darauf, dass ${}r\geq s$ genau dann gilt, wenn ${}r-1\geq s-1$ ist. Dies ermöglicht einen Induktionsbeweis.

Beispiel

Wir wollen überprüfen, ob die Inhalte von zwei Registern ${}R_{i}$ und ${}R_{j}$ übereinstimmen. Dazu kann man das Programm aus Beispiel einfach abändern zu

1. ${}C(j,6)$
2. ${}j-$
3. ${}C(i,9)$
4. ${}i-$
5. Gehe zu ${}1$
6. ${}C(i,8)$
7. Gehe zu ${}9$
8. ${}k+$
9. Halte an

Bei Gleichheit erhält man ${}r_{k}=1$, bei Ungleichheit ${}r_{k}=0$.

In den obigen beiden Beispielen wurde die Antwort im Register ${}R_{k}$ (in der Form ${}0$ oder ${}1$ abgespeichert). Der Druckbefehl nimmt aber immer Bezug auf ${}R_{1}$. Daher ist es nötig, Registerinhalte in andere Register zu verschieben.

Beispiel

Wir wollen den Registerinhalt ${}r_{i}$ des Registers ${}R_{i}$ in das Register ${}R_{j}$ übertragen (unabhängig von dessen Inhalt). Dies leistet das folgende Programm.

1. Leere ${}R_{j}$
2. ${}C(i,6)$
3. ${}i-$
4. ${}j+$
5. Gehe zu ${}2$
6. Halte an

Bei diesem Programm wird im Laufe der Durchführung das Ausgangsregister der Übertragung leer gemacht. Dies ist nicht immer erwünscht, häufig möchte man den Inhalt eines Registers kopieren und sich den Inhalt zugleich merken.

Beispiel

Wir wollen den Registerinhalt ${}r_{i}$ des Registers ${}R_{i}$ in das Register ${}R_{j}$ übertragen (unabhängig von dessen Inhalt), ohne ${}R_{i}$ zu leeren. Dazu brauchen wir ein drittes Register ${}R_{k}$ und das folgende Programm.

1. Leere ${}R_{j}$
2. Leere ${}R_{k}$
3. ${}C(i,8)$
4. ${}i-$
5. ${}j+$
6. ${}k+$
7. Gehe zu ${}3$
8. Übertrage den Inhalt von ${}R_{k}$ nach ${}R_{i}$
9. Halte an

Hier wird zwar im Laufe des Programms der Inhalt von ${}R_{i}$ verändert, zum Schluss wird der ursprüngliche Inhalt aber wieder hergestellt.

Beispiel

Die beiden Registerinhalte ${}r_{i}$ (von ${}R_{i}$) und ${}r_{j}$ (von ${}R_{j}$) sollen addiert werden, wobei die Summe zum Schluss in ${}R_{k}$ stehen soll (es seien $i,j,k$ paarweise verschieden). Dies leistet das folgende Programm.

1. Leere ${}R_{k}$
2. Übertrage ${}r_{i}$ nach ${}R_{k}$
3. ${}C(j,7)$
4. ${}j-$
5. ${}k+$
6. Gehe zu ${}3$
7. Halte an

Mit der Addition und der Kopie von Inhalten kann man auch den Inhalt eines Registers zu einem anderen Register dazuaddieren. Dies kann man natürlich auch einfach direkt realisieren.

Beispiel

Die beiden Registerinhalte ${}r_{i}$ (von ${}R_{i}$) und ${}r_{j}$ (von ${}R_{j}$) sollen multipliziert werden, wobei das Produkt zum Schluss in ${}R_{k}$ stehen soll (es seien $i,j,k$ paarweise verschieden). Dies leistet das folgende Programm mit dem Hilfsregister ${}R_{\ell }$.

1. Leere ${}R_{k}$
2. Übertrage den Inhalt von ${}R_{i}$ nach ${}R_{\ell }$ ohne ${}R_{i}$ zu leeren
3. ${}C(j,7)$
4. Addiere den Inhalt von ${}R_{\ell }$ zu ${}R_{k}$ hinzu
5. ${}j-$
6. Gehe zu ${}2$
7. Halte an

Die Korrektheit dieses Programms beruht auf ${}r\cdot s=(r-1)s+s$; für das Produkt ${}rs$ muss man ${}r$-mal ${}s$ mit sich selbst addieren.

Beispiel

Es soll überprüft werden, ob der Registerinhalt ${}r_{t}$ (von ${}R_{t}$) den Registerinhalt ${}r_{j}$ (von ${}R_{j}$) teilt. Falls ja soll das Programm ${}1$ ausgeben, andernfalls ${}0$. Dies leistet das folgende Programm mit den Hilfsregistern ${}R_{k}$ und ${}R_{\ell }$ (für Teilprogramme braucht man noch weitere Hilfsregister). Das Ausgaberegister ${}R_{1}$ soll zu Beginn leer sein.

1. Leere ${}R_{\ell }$
2. Berechne ${}r_{t}\cdot r_{\ell }$ und schreibe das Ergebnis in ${}R_{k}$ (ohne ${}r_{t},r_{\ell }$ zu verändern)
3. Bei ${}r_{k}>r_{j}$ gehe zu 8
4. Bei ${}r_{k}=r_{j}$ gehe zu 7
5. ${}\ell +$
6. Gehe zu 2
7. ${}1+$
8. Drucke
9. Halte an

Beispiel

Es soll überprüft werden, ob der Registerinhalt ${}r_{j}$ (von ${}R_{j}$) eine Primzahl ist. Falls ja soll das Programm ${}1$ ausgeben, andernfalls ${}0$. Dies leistet das folgende Programm mit dem Hilfsregister ${}R_{t}$ (für Teilprogramme braucht man noch weitere Hilfsregister). Das Ausgaberegister ${}R_{1}$ soll zu Beginn leer sein.

1. Leere ${}R_{t}$
2. ${}t+$
3. ${}t+$
4. Wenn ${}r_{t}=r_{j}$, so gehe zu 8
5. Wenn ${}r_{t}\geq r_{j}$, so gehe zu 9
6. Wenn ${}r_{j}$ von ${}r_{t}$ geteilt wird, so gehe zu 9
7. Gehe zu 3
8. ${}1+$
9. Drucke
10. Halte an

Beispiel

Es sollen die geraden Zahlen ${}\geq 4$ daraufhin überprüft werden, ob sie die Eigenschaft in der Goldbachvermutung erfüllen, also ob sie die Summe von zwei Primzahlen sind. Das Programm soll die Ausgabe ${}0$ machen, falls ein Gegenbeispiel gefunden wurde. Dies leistet das folgende Programm mit den Registern ${}R_{n}$, ${}R_{k}$ und ${}R_{i}$, die alle zu Beginn auf ${}0$ gesetzt seien. Auch das Ausgaberegister ${}R_{1}$ soll zu Beginn leer sein. Wir testen ab ${}6$, um uns auf ungerade Primzahlen als Summanden beschränken zu können.

1. ${}n++++$
2. ${}n++$
3. Leere ${}R_{k}$
4. ${}k+$
5. ${}k++$
6. Wenn ${}r_{k}\geq r_{n}$, so gehe zu 12
7. Wenn ${}r_{k}$ eine Primzahl ist, so gehe zu 9
8. Gehe zu 5
9. Berechne ${}r_{n}-r_{k}$, schreibe das Ergebnis in ${}R_{i}$
10. Wenn ${}r_{i}$ eine Primzahl ist, so gehe zu 2
11. Gehe zu 5
12. Drucke
13. Halte an