Frage:
Sei \( L_\# \) die folgende unentscheidbare Sprache:
\( L_\# = \{〈M〉| M \) schreibt für Eingabe irgendwann das Symbol # auf das Band} Wir wollen nun eine Reduktion vom speziellen Halteproblem \( H_ε \) auf \( L_\# \) beschreiben und damit zeigen, dass \( L_\# \) nicht entscheidbar ist.
Ansatz:
„Für eine Turingmaschine M, als Eingabe für \( L_\# \), konstruieren wir eine Turingmaschine M′ als Eingabe für \( H_ε \) wie folgt:
1.M′hat das gleiche Bandalphabet wie M.
2.M′hat die gleiche Zustandsmenge wie M mit einem zusätzlichen Zustand \( q_e \).
3.Die Überführungsfunktion von M ′ist die von M mit den Ausnahmen:
• Zustand \( q_e \) hat für alle Übergänge eine Endlosschleife auf sich selbst.
→M′wird niemals halten, sobald sie in \( q_e \) ist.
• Jede Regel, bei der gehalten wird bzw. die undefiniert ist, wird durch die Regel ‘gehe inZustand \( q_e \)’ ersetzt.
•Jede Regel, bei der ein # geschrieben wird, wird durch die Regel ‘halte’ ersetzt.Damit ist bewiesen, dass M gestartet auf dem leeren Band genau dann ein # schreibt, wenn M′ gestartet auf dem leeren Band hält. Nach dem Reduktionsprinzip folgt, dass die Sprache \( L_\# \) nicht entscheidbar ist.“
Da ist irgendwo ein Fehler drin, aber ich find' ihn nicht wie Nachbars Lumpi.
