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

Aus Wikiversity
Zur Navigation springen Zur Suche springen

Wir ordnen die endlich vielen, sagen wir , Zahlen aus in aufsteigender Reihenfolge, also

Wir setzen

und

für . Die sind also einfach die Differenzen zwischen den aufeinanderfolgenden Zahlen aus , und es ist

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

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

(wobei als zu lesen ist) oder aber

In den ersten Programmblöcken bleibt der Inhalt des Registers positiv, da ja insgesamt nur

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

Bei

ist

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

ist

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 wird erhöht und anschließend wird angehalten mit einen positivem Inhalt des ersten Registers.
Zur gelösten Aufgabe