One post tagged with "automata theory"

Oft wird der Nachweis, dass das Halteproblem nicht entscheidbar ist, in der Fachliteratur (Schöning [📖Sch08, p. 119 f.], Asteroth und Baier [📖BA02, p. 106 f.], Sipser [📖Sip12, p. 216 f.]) mithilfe einer Turingmaschine und einem Widerspruchsbeweis gezeigt, in etwa:

Angenommen,

ist entscheidbar.

Sei $T'$ ist die Turingmaschine, die $K'$ entscheidet.
Sei $w = \langle T \rangle$ die Codierung¹ 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 \notin K'$)
  • $T$ stoppt nicht, wenn $T'$ die Eingabe $w$ akzeptiert ($w \in K'$)

Damit folgt: $T$ stoppt bei Eingabe $w$ $\Leftrightarrow$ $T'$ verwirft $w$ $\Leftrightarrow$ $w \notin K'$ $\Leftrightarrow$ $T$ stoppt nicht

Widerspruch!