Registermaschine/Größenvergleich von zwei Registerinhalten/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.