Wir ordnen die endlich vielen, sagen wir
, Zahlen aus
in aufsteigender Reihenfolge, also
-
![{\displaystyle {}n_{1}<n_{2}<n_{3}<\cdots <n_{s-1}<n_{s}\,.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/30ae2748a59dd47851a4034fe18a16fb0ea57ea4)
Wir setzen
-
![{\displaystyle {}d_{1}:=n_{1}\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8d007777b00a0848330df778e7d914e7c3b81a5a)
und
-
![{\displaystyle {}d_{i}:=n_{i}-n_{i-1}\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3aa79747dfe430f2953d715830f3001b6e363ffe)
für
.
Die
sind also einfach die Differenzen zwischen den aufeinanderfolgenden Zahlen aus
, und es ist
-
![{\displaystyle {}n_{i}=d_{1}+d_{2}+\cdots +d_{i}\,.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/192cf1b771097560e6954bcceb06509f9e310955)
Wir erstellen das Programm mit Hilfe von
Programmblöcken der Länge
der Form
-
-
-
-
-
-
-
-
-
Der Inhalt von
wird also abwechselnd um
reduziert und abwechselnd wird gefragt, ob der Inhalt leer ist, wobei im leeren Fall auf die Befehlszeile
verwiesen, aber die allerletzte Abfrage des Blockes auf die
-te Befehlszeile verweist. Bei
-
![{\displaystyle {}d_{1}=1\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b45bd261f79cf9da3f8954164c0db3911b7e02bc)
besteht der erste Block allein aus
. Diese
Blöcke werden hintereinander geschrieben, und das Programm wird durch
-
-
abgeschlossen.
Die Wirkungsweise des Programms macht man sich folgendermaßen klar. Zu jedez zu testenden Zahl
gibt es ein eindeutiges
mit
-
![{\displaystyle {}n_{i-1}<n\leq n_{i}\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bcf7fcc03a11ed76e5b0decc6a91b549ee7981a7)
(wobei
als
zu lesen ist)
oder aber
-
![{\displaystyle {}n>n_{s}\,.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1639226ea326644bccd69236912fce0a6d209fd5)
In den ersten
Programmblöcken bleibt der Inhalt des Registers positiv, da ja insgesamt nur
-
![{\displaystyle {}n_{i-1}=d_{1}+\cdots +d_{i-1}\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/48dcbf420aa6105c0f9111ba4762baf138b150e5)
von
abgezogen wird. Daher gelangt man in den entscheidenden
-ten Block. Wenn dieser Block begonnen wird, steht im Register der Wert
, und für diesen Wert gilt
-
![{\displaystyle {}0<n-n_{i-1}\leq n_{i}-n_{i-1}=d_{i}\,.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1d85bb8e9281e6f8e7cec586a26725c9fbc26e47)
Bei
-
![{\displaystyle {}n<n_{i}\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d25d617ad9c1652bdaf0cf96e1b10cdf39232818)
ist
-
![{\displaystyle {}n-n_{i}<d_{i}\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e904ab7008ec397fea44bb45934da560b382f895)
so dass durch das Abziehen in diesem Block die
erreicht wird, und zwar vor dem vorletzten Befehl des Blocks, so dass nach
umgeleitet wird. Dort wird um
erhöht
(was nur bei
benötigt wird)
und das Endergebnis ist nicht
, was korrekt ist.
Bei
-
![{\displaystyle {}n=n_{i}\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/87229dafe8ab02bf8c352abd03b3dbcd01e09e9e)
ist
-
![{\displaystyle {}n-n_{i}=d_{i}\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/72d9621980f6d3b476c65c894022b474f23633a7)
so dass durch das Abziehen in diesem Block die
erreicht wird, und zwar genau im vorletzten Befehl des Blocks. Im nächsten Befehl wird nach
umgeleitet und das Programm hält an mit der
als Ausgabe, was auch korrekt ist. Bei
werden alle Blöcke ohne Umleitung durchlaufen, in
![{\displaystyle {}h-1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8fa581af03822e292e9b1c49eebd033d80f01fcd)
wird erhöht und anschließend wird angehalten mit einen positivem Inhalt des ersten Registers.