Registermaschine/Entscheidbarkeit und Aufzählbarkeit/Fakt/Beweis

Beweis

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

Es seien nun ${}T$ als auch ${}\mathbb {N} \setminus T$ aufzählbar, und es seien ${}P$ und ${}Q$ Programme, die dies leisten. Dann liefert die folgende Kombination der beiden Programme ein Entscheidungsverfahren: Man schreibt die Programme ${}P$ und ${}Q$ 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 ${}n$ übereinstimmt, weiß man, ob ${}n$ zu ${}T$ gehört oder nicht. Da ${}n$ entweder zu ${}T$ oder zum Komplement gehört, muss einer dieser Fälle eintreten.

Zur bewiesenen Aussage