Lemma 1

• Zustandsübergangsgraph enthalte folgende Struktur ₨:

• Wenn Z erreicht und Bandinhalt bekannt, dann ist Halteproblem entscheidbar (ab diesem Punkt)

• Beweis:

  • Gelesenes Zeichen sei x
  • Fallunterscheidung…

Notizen: