N/Endliche Teilmenge/Entscheidbar/Nur ein Register/Aufgabe/Lösung

Wir ordnen die endlich vielen, sagen wir ${}s$, Zahlen aus ${}T$ in aufsteigender Reihenfolge, also

${}n_{1}<n_{2}<n_{3}<\cdots <n_{s-1}<n_{s}\,.$

Wir setzen

${}d_{1}:=n_{1}\,$

und

${}d_{i}:=n_{i}-n_{i-1}\,$

für ${}i=2,\ldots ,s$. Die ${}d_{i}$ sind also einfach die Differenzen zwischen den aufeinanderfolgenden Zahlen aus ${}T$, und es ist

${}n_{i}=d_{1}+d_{2}+\cdots +d_{i}\,.$

Wir erstellen das Programm mit Hilfe von ${}s$ Programmblöcken der Länge ${}2d_{i}$ der Form

$\,\,1-$

$\,\,C(1,h-1)$

$\,\,1-$

$\,\,C(1,h-1)$

$\vdots$

$\,\,1-$

$\,\,C(1,h-1)$

$\,\,1-$

$\,\,C(1,h).$

Der Inhalt von ${}R_{1}$ wird also abwechselnd um ${}1$ reduziert und abwechselnd wird gefragt, ob der Inhalt leer ist, wobei im leeren Fall auf die Befehlszeile ${}h-1$ verwiesen, aber die allerletzte Abfrage des Blockes auf die ${}h$-te Befehlszeile verweist. Bei

${}d_{1}=1\,$

besteht der erste Block allein aus ${}C(1,h)$. Diese ${}s$ Blöcke werden hintereinander geschrieben, und das Programm wird durch

$h-1.\,\,1+$

$h.\,\,{\text{Halte an}}$

abgeschlossen.

Die Wirkungsweise des Programms macht man sich folgendermaßen klar. Zu jedez zu testenden Zahl ${}n\in \mathbb {N}$ gibt es ein eindeutiges ${}i$ mit

${}n_{i-1}<n\leq n_{i}\,$

(wobei ${}n_{-1}$ als ${}0$ zu lesen ist) oder aber

${}n>n_{s}\,.$

In den ersten ${}i-1$ Programmblöcken bleibt der Inhalt des Registers positiv, da ja insgesamt nur

${}n_{i-1}=d_{1}+\cdots +d_{i-1}\,$

von ${}n$ abgezogen wird. Daher gelangt man in den entscheidenden ${}i$-ten Block. Wenn dieser Block begonnen wird, steht im Register der Wert ${}n-n_{i-1}$, und für diesen Wert gilt

${}0<n-n_{i-1}\leq n_{i}-n_{i-1}=d_{i}\,.$

Bei

${}n<n_{i}\,$

ist

${}n-n_{i}<d_{i}\,$

so dass durch das Abziehen in diesem Block die ${}0$ erreicht wird, und zwar vor dem vorletzten Befehl des Blocks, so dass nach ${}h-1$ umgeleitet wird. Dort wird um ${}1$ erhöht (was nur bei $n=0\notin T$ benötigt wird) und das Endergebnis ist nicht ${}0$, was korrekt ist.

Bei

${}n=n_{i}\,$

ist

${}n-n_{i}=d_{i}\,$

so dass durch das Abziehen in diesem Block die ${}0$ erreicht wird, und zwar genau im vorletzten Befehl des Blocks. Im nächsten Befehl wird nach ${}h$ umgeleitet und das Programm hält an mit der ${}0$ als Ausgabe, was auch korrekt ist. Bei ${}n>n_{s}$

werden alle Blöcke ohne Umleitung durchlaufen, in ${}h-1$ wird erhöht und anschließend wird angehalten mit einen positivem Inhalt des ersten Registers.

Zur gelösten Aufgabe