Registermaschine/Entscheidbarkeit und Aufzählbarkeit/Fakt/Beweis

Beweis

Wenn ein Programm ist, das entscheidet, so kann man einfach ein aufzählendes Programm konstruieren. Man lässt der Reihe nach jede natürliche Zahl mittels auf ihre Zugehörigkeit zu überprüfen und druckt sie aus, falls sie dazu gehört (dazu muss man den Haltebefehl von zu einer Druckausgabe modifizieren). Entsprechend konstruiert man ein Aufzählungsprogramm für das Komplement.

Es seien nun als auch aufzählbar, und es seien und Programme, die dies leisten. Dann liefert die folgende Kombination der beiden Programme ein Entscheidungsverfahren: Man schreibt die Programme und hintereinander (wobei man natürlich die adressierten Register und Programmzeilen umnummerieren muss) und lässt sie abwechselnd bis zu einer Druckausgabe laufen. Sobald eine Druckausgabe eines Programmteils mit der zu überprüfenden Zahl übereinstimmt, weiß man, ob zu gehört oder nicht. Da entweder zu oder zum Komplement gehört, muss einer dieser Fälle eintreten.