Halteproblem/Registermaschine/Einführung/Kodierung/Textabschnitt

Nicht jedes Programm hält an. Ein einfaches Beispiel mit zwei Registern ${}R_{1},R_{2}$ und leerer Belegung für ${}R_{2}$ ist

1. ${}1+$
2. ${}C(2,1)$
3. Halte an

Im Allgemeinen wird es sehr schnell schwierig, zu einem gegebenen konkreten Programm zur Eingabe ${}r_{1}=0$ zu entscheiden, ob es den Haltebefehl schließlich erreicht oder nicht. Ebenso ist es schwierig zu entscheiden, für welche Eingabedaten in ${}R_{1}$ (den Input) das konkrete Programm stoppt. Wenn man das Programm bei einer bestimmten Eingabe laufen lässt und es nach einer gewissen Zeit anhält, so kann man dies natürlich unmittelbar als einen Beweis für die Halteeigenschaft des Programms verstehen. Wenn das Programm nicht die Halteeigenschaft hat, so kann man dies aus dem Programmablauf nicht erschließen. Das Programm läuft einfach weiter und man weiß nicht, ob es einfach noch nicht angehalten hat oder ob es niemals anhalten wird. Mit einer aufwändigen Analyse des Programms wird man im Allgemeinen erkennen können, ob das Programm anhält oder nicht.

Ein qualitativ anderes Problem ist allerdings die Frage, ob es ein deterministisches Verfahren gibt, mit dem man für jedes Programm (bzw. jedes Programm und jede Eingabe) entscheiden kann, ob es anhält oder nicht.

Hier deutet sich eine selbstbezügliche Fragestellung an: Gibt es ein Programm, das Aussagen über alle Programme machen kann? Welche Aussage macht dann dieses Programm über sich selbst?

Um einen solchen Ansatz präzise machen zu können, müssen wir Programme als Eingabe für ein Programm interpretieren können. Das Programm einer Registermaschine erlaubt nur die Eingabe einer Zahl. Daher müssen wir ein Programm durch eine Zahl kodieren. Dies geschieht in zwei Schritten.

Zuerst führen wir für die erlaubten Befehle abkürzende Schreibweisen ein. Wir arbeiten mit dem Alphabet

$\prime \,-\,I\,D\,C\,P\,H\,,$

Die einzelnen Befehle werden folgendermaßen notiert

1. Inkrementierung von ${}R_{i}$: ${}I\prime \prime \cdots \prime$ (mit ${}i$ Strichen).
2. Dekrementierung von ${}R_{i}$: ${}D\prime \prime \cdots \prime$ (mit ${}i$ Strichen).
3. Sprunganweisung ${}C(i,j)$: ${}C\prime \prime \cdots \prime ,\prime \prime \cdots \prime$ (mit ${}i$ Strichen vor dem Komma und ${}j$ Strichen nach dem Komma).
4. Druckanweisung: ${}P$.
5. Halteanweisung: ${}H$.

Das Symbol ${}\prime$ wird also benutzt, um sowohl die Registernummern als auch die Zeilennummern (in der Sprunganweisung) auszudrücken. Da in jeder Befehlszeile eines konkreten Programmes konkrete Register bzw. Zeilen adressiert werden, stehen da jeweils natürliche Zahlen (keine Variablen), die problemlos durch eine Strichfolge ausgedrückt werden können.

Ein Programm, das aus den durchnummerierten Befehlszeilen ${}B_{1},B_{2},\ldots ,B_{h}$ besteht, wird dann insgesamt durch die Zeichenfolge

$b_{1}-b_{2}-\ldots -b_{h}$

wiedergegeben, wobei ${}b_{j}$ die soeben angeführte Kodierung der ${}j$-ten Befehlszeile ist. Das Zeichen ${}-$ wird also verwendet, um die Zeilen voneinander zu trennen. Das Mitschleppen der Zeilennummern ist nicht nötig, da sich die Nummer aus der Reihenfolge rekonstruieren lässt.

Das oben angegebene Programm hätte demnach die symbolische Kodierung

$I\prime -C\prime \prime ,\prime -H$

In einem zweiten Schritt ersetzen wir diese symbolische Kodierung durch eine numerische Kodierung. Dafür gibt es verschiedene Möglichkeiten. Da unser Alphabet, mit dem wir jedes Programm schreiben können, ${}8$ Symbole verwendet, liegt eine Repräsentierung im Achtersystem nahe. Da die ${}0$ als Anfangsnummer etwas problematisch ist, arbeiten wir lieber im Neunersystem (man kann die folgenden Zahlen genauso gut im Zehnersystem auffassen) und ordnen den Symbolen von oben in der obigen Reihenfolge die Ziffern

$1,2,3,4,5,6,7,8$

zu. Das Programm von oben wird dann zur Ziffernfolge

$3125118127.$

Die einem jeden Programm ${}P$ auf diese Weise zugeordnete Zahl (also der Zahlwert, nicht die Ziffernfolge) nennen wir ${}c(P)$. Man spricht von der Gödelnummer des Programms.