Heruntergebrochen beschreibt das Halteproblem ein Programmüberprüfendes Programm welches sich selbst überprüfen soll.
Wird eine Endlosschleife beim Überprüfen festgestellt, ist das Programm endlos, wird keine festgestellt soll eine Endlosschleife gestartet werden. Vereinfacht ist dies ein Inverter für den Fall, ob eine Endlosschleife erzeugt wird. Demzufolge wird der Inverter invertiert. Beispiel: Programm ohne Endlosschleife wird zu einem Programm mit Endlosschleife, welches wiederum zu einem Programm ohne Endlosschleife wird. Fazit: Endlosschleife = keine Endlosschleife Annahme: Besagtes Programm überprüft sich selbst und stellt eine Endlosschleife fest, da die Vorschrift bei keiner Endlosschleife vorsieht eine zu erzeugen.
Fazit: Der Inverter wird diese Endlosschleife allerdings nicht ausführen. Damit wird das potentiell endlose Programm beendet. Dem Halteproblem wurde Einhalt geboten.