0 Daumen
42 Aufrufe

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.

von

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community