Indirekter Beweis: Falls das Halteproblem doch algorithmisch lösbar ist:
Dann definieren wir das Programm falls (Das Programm mit Nummer , gestartet mit Eingabe ) hält, dann irgendeine nicht haltende Rechnung (Schleife), sonst 0.
Das Programm hat auch eine Nummer, diese sei . Also .
Hält ? Wegen der Fallunterscheidung gilt hält hält nicht hält nicht!
Das ist ein Widerspruch, d. h. (wenigstens) eine Annahme war falsch: ist gar nicht programmierbar!