Oft wird der Nachweis, dass das Halteproblem nicht entscheidbar ist, in der Fachliteratur (Schöning [📖Sch08, 119 f.], Asteroth und Baier [📖BA02, 106 f.], Sipser [📖Sip12, 216 f.]) mithilfe einer Turingmaschine und einem Widerspruchsbeweis gezeigt, in etwa:
Angenommen,
K′={w∈Σ∗∣w=⟨T⟩,T stoppt bei Eingabe w}
ist entscheidbar.
Sei T′ ist die Turingmaschine, die K′ entscheidet.
Sei w=⟨T⟩ die Codierung1 einer Turingmaschine, die wie folgt arbeitet:
- T simuliert das Verhalten von T′ bei der Eingabe w:
- T stoppt, wenn T′ die Eingabe w verwirft (w∈/K′)
- T stoppt nicht, wenn T′ die Eingabe w akzeptiert (w∈K′)
Damit folgt:
T stoppt bei Eingabe w ⇔ T′ verwirft w ⇔ w∈/K′ ⇔ T stoppt nicht
Widerspruch!