Skip to main content

One post tagged with "automata theory"

View All Tags

[DE] Betrachtung des Widerspruchsbeweis des speziellen Halteproblems nach Vossen und Witt

· 6 min read

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}K' = \{w \in \Sigma^* | w = \langle T \rangle, \text{$T$ stoppt bei Eingabe $w$}\}

ist entscheidbar.

Sei T′T' ist die Turingmaschine, die K′K' entscheidet.
Sei w=⟨T⟩w = \langle T \rangle die Codierung1 einer Turingmaschine, die wie folgt arbeitet:

  • TT simuliert das Verhalten von T′T' bei der Eingabe ww:
    • TT stoppt, wenn T′T' die Eingabe ww verwirft (w∉K′w \notin K')
    • TT stoppt nicht, wenn T′T' die Eingabe ww akzeptiert (w∈K′w \in K')

Damit folgt: TT stoppt bei Eingabe ww ⇔\Leftrightarrow T′T' verwirft ww ⇔\Leftrightarrow w∉K′w \notin K' ⇔\Leftrightarrow TT stoppt nicht

Widerspruch!

Footnotes​

  1. Anstatt Gödelnummer wird im Folgenden auch einfach der Begriff Codierung verwendet, wobei streng genommen τ(T)\tau(T) die Codierung einer normierten Turingmaschine ist, bevor ihr eine Gödelnummer zugewiesen wird ↩