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

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