 Selbsthalteproblem |
donvito
Mitglied
Dabei seit: 04.01.2007
Beiträge: 41
Herkunft: Freiburg
 |
|
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?
__________________
Meine Moviebase
|
|
17.03.2008 18:12 |
|
|
Tobias
Routinier
Dabei seit: 18.09.2006
Beiträge: 324
|
|
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') ?
|
|
|
17.03.2008 19:08 |
|
|
donvito
Mitglied
Dabei seit: 04.01.2007
Beiträge: 41
Herkunft: Freiburg
|
|
Hmm, ich würde sagen HALTETEST(M') hält, ist aber bissel verzwickt, da sich das ganze ja quais endlos selbst aufruft.
__________________
Meine Moviebase
|
|
|
17.03.2008 19:30 |
|
|
Tobias
Routinier
Dabei seit: 18.09.2006
Beiträge: 324
|
|
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
|
|
|
17.03.2008 19:42 |
|
|
|
