---

Geschrieben von donvito am 17.03.2008 um 18:12:

  Selbsthalteproblem

Wie löse ich diese Aufgabe:
Zeigen Sie, dass die Sprache
HALT_Selbst = {<M> | DTM M hält auf Eingabe <M>}
nicht entscheidbar ist?

Ich habe versucht so zu argumentieren:
^Das "normale" Halteproblem ist wie folge definiert: {<M, w> |M ist eine TM und hält auf Eingabe w}. Dieses ist laut Vorlesung nicht entscheidbar. Angenommen, es gibt eine TM, die HALT entscheidet. Dann entscheidet diese TM auch HALT_Selbst, denn letzlich ist die Codierung einer Maschine nichts anderes als ein x-beliebiges Wort, da die TM nicht erkennen kann, ob es sich um ihre eigene Codierung handelt.
Da jedoch das Halteproblem nicht entscheidbar ist, ist auch das Selbsthalteproblem nicht entscheidbar.

Was kann man hier noch verbessern? Stimmt das so überhaupt?

---

Geschrieben von Tobias am 17.03.2008 um 19:08:

 

Deine Reduktionrichtung ist falsch.

Du sagst: HALT nicht entscheidbar => HALT_Selbst nicht entscheidbar

Das ist falsch, denn HALT_Selbst ist eine Einschränkung des allgemeinen Problems, also ein Spezialfall von HALT.

Verallgemeinert gilt: Ist S ein Spezialfall von A, dann gilt:
S nicht entscheidbar => A nicht entscheidbar
A entscheidbar => S entscheidbar
die anderen Folgerungsrichtungen sind im Allgemeinen nicht zutreffend.

Es handelt sich bei dem gesuchten Beweis um den Beweis der Nichtentscheidbarkeit des speziellen Halteproblems. Man führt ihn durch Konstruktion eines Paradoxons.

Er geht so:

Nimm an, das Problem HALT_Selbst wäre entscheidbar. Dann gäbe es eine Turingmaschine HALTETEST, die folgende Funktion berechnet:

HALTETEST(TM M) = 1 falls M hält auf <M>
HALTETEST(TM M) = 0 falls M hält nicht auf <M>

Jetzt konstruieren wir eine TM M', die HALTETEST als Unterprogramm verwendet:

M'(TM M):
Falls HALTETEST = 1 gehe in Endlosschleife
Sonst terminiere.

Was passiert nun bei Aufruf von HALTETEST(M') ?

---

Geschrieben von donvito am 17.03.2008 um 19:30:

 

Hmm, ich würde sagen HALTETEST(M') hält, ist aber bissel verzwickt, da sich das ganze ja quais endlos selbst aufruft.

---

Geschrieben von Tobias am 17.03.2008 um 19:42:

 

Du musst das Paradoxon erkennen:

M' hält auf Eingabe M nur, wenn M auf <M> nicht hält, also HALTETEST(M) = 0 gilt.

HALTETEST(M') = 1 --> M' hält auf <M'> --> HALTETEST(M') = 0

HALTETEST(M') = 0 --> M' hält auf <M'> nicht --> HALTETEST(M') = 1