Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Reduktion SS 14
Hallo alle zusammen ,
mal eine Frage wegen Reduktion .
L2b = { | M ist eine deterministische 1-Band Turingmaschine, und es gibt genau ein z ∈ {0,1}*, so dass M gestartet mit z NICHT hält} ist gegeben , und möchten mittels Reduktion auf H-epsilon zeigen , dass L2b nicht entscheidbar ist .
so meine Lösung :
f(x) : <FMw> falls x=w
< FM2 > sonst
f ist total berechenbar .
FMw :
1.Eingabe sei y
2. Starte M mit leerem Band
3. if y !=z halte ( wobei z ist die Eingabe von Definition L2b )
4. sonst Endlosschleife
FM2:
1.Eingabe sei y
2.Endlosschleife
Fall 1 : x∊H-epsilon /\ x=w → f(x) = <FMw> → M hält → if y=z endlosschleide , sonst FMw hält → f(x) ∊ L2b
Fall 2 : x!∊H-epsilon /\ x=w → f(x) = <FMw> → M hält nicht → FMw hält nicht → f(x) !∊ L2b
Fall 3 : x∊H-epsilon /\ x!=w → f(x) = → hält nicht → f(x) !∊L2b
somit gilt x∊H-epsilon <–> f(x)∊L2b
ich weiss echt nicht , ob das so stimmt … ich finde es logisch , aber Lösung davon ist ganz anderes im Forum …
kann jemand mir sagen , ob das stimmt , wenn nicht , warum und wo … und wie am besten zu machen ? …
vielen Dank im Voraus
MfG
Ich denke, deine Lösung stimmt größtenteils.
Kleine Anmerkung: Elemente aus H_epsilon und L2b sind Gödelnumern von TM (), nicht Gödelnummern von TM mit Eingabe (w). Die Reduktionsfunktion würde also folgendermaßen aussehen:
f(x) : <FM<M>> falls x=<M>
<FM2> sonst Und die Fallunterscheidung dementsprechend:
Fall 1: x ∊ H_epsilon /\ x= → f(x) = <FM> → M hält → if y=z Endlosschleife, sonst FM hält → f(x) ∊ L2b
Fall 2: …
Weiterhin ist die Bedingung für Fall 3 (x ∊ H-epsilon /\ x != ) nie erfüllt, da jedes Element aus H_epsilon eine gültige Gödelnummer für eine TM sein muss. x kann also nicht gleichzeitig in H_epsilon sein und keine TM kodieren. Die korrekte Bedingung würde einfach lauten: x != .
Eine andere Lösung wäre, die feste Maschine folgendermaßen zu konstruieren:
FM<M>:
1. Eingabe sei y
2. Wenn y == z dann Endlosschleife (wobei z ist die Eingabe von Definition L2b)
3. Starte M mit leerem Band
4. halteDas ist möglicherweise der Ansatz, der an einer anderen Stelle hier im Forum gewählt wurde. Dadurch verändert sich natürlich auch die Argumentation, warum die gewählte Reduktionsfunktion das initiale Halteproblem auf L2b reduziert. Korrekt ist allerdings beides.
Noch ein Hinweis: Du hättest die feste Maschine auch folgendermaßen definieren können:
FM<M>:
1. Eingabe sei y
2. Starte M mit leerem Band
3. Wenn y != "100101110" dann halte
4. sonst EndlosschleifeDie Definition von L2b fordert nur, dass es genau ein z gibt, für das die TM nicht hält. Welches z das ist wird allerdings nicht vorgegeben und ist deshalb auch nicht als EIngabe/Parameter der Definition L2b zu verstehen.
1 „Gefällt mir“
so noch was kleines … macht das ein Unterschied worauf wir reduzieren möchten ob es H-epsilon oder H-quer ist oder H selbst … ( ich weiss , dass jede für einen anderen Ziel zu benutzen ist ) … aber ich meine von Vorgehensweise um Reduktion zu machen ? …
und was wäre es , wenn die Maschine gar nicht haltet und nur schreibt 
?
und wie hast das bestimmt , dass die Elemente von H-epsilon und L2b Gödelnummern von TM ohne Eingabe ist . ( das interessiert mich mal , da ich die ganze Zeit da was falsch schriebe ) .
Die Vorgehensweise ist immer gleich. Lediglich die Aussage der Reduktion ändert sich. Wenn du H-quer auf L (H-quer <= L) reduzierst heißt das, dass L nicht rekursiv aufzählbar ist. Wenn du H auf L reduzierst heißt das, dass L nicht entscheidbar ist. Aufpassen musst du nur bei Polynomialzeitreduktionen (Wenn du also zeigen willst, dass L NP-schwer ist und dafür SAT auf L reduzierst), da hier die Reduktionsfunction f in Polynomialzeit berechnet werden können muss (Also f ∊ O(n^k) für ein k).
Ich verstehe nicht genau, was du meinst. Geht es darum, eine Maschine, die niemals hält, in einer Reduktion zu verwenden?
Das kannst du an der Definition der Menge ablesen:
L2b = { | M ist eine det. 1-Band-TM … }
Vor dem senkrechten Strich steht (fettgedruckt), was für Elemente überhaupt in der Menge auftauchen können. In diesem Fall sind das Gödelnummern von M. Bis jetzt ist noch nicht gesagt, was genau M ist. Nach dem senkrechten Strich werden dann weitere Bedingungen für gestellt. soll also nicht die Gödelnummer eines beliebigen M sein, sondern die Gödelnummer einer det. 1-Band-TM (Das ist nicht selbstverständlich, es könnte sich z.B. auch um die Gödelnummer eines Kellerautomaten handeln). Jetzt ist schonmal klar, dass in L2b nur Gödelnummern von det. 1-Band-TM auftauchen können. Danach kommen noch weitere Bedingungen, die die Elemente von L2b noch mehr einschränken.
Die Definition von H_epsilon sieht ähnlich aus:
H_epsilon = { | M ist eine det. 1-Band-TM, die gestartet mit leerem Band hält. }
Auch hier können wieder nur Gödelnummern von M in der Menge auftauchen, wobei M eine det. 1-Band-TM sein muss.
Die Definition des Halteproblems hingegen:
H = { w | M ist eine det. 1-Band-TM, die gestartet mit w hält. }
Elemente von H sind Gödelnummern von M gefolgt von einem w. M muss dabei wieder eine det. 1-Band-TM sein. Für w werden keine Bedingungen formuliert, also können wir w als eine beliebige Folge von Zeichen behandeln. Die Elemente von H sind also Gödelnummern von det. 1-Band-TM gefolgt von einer beliebigen Zeichenkette.
ja geht um eine Maschine, die niemals hält, in einer Reduktion zu verwenden 
… kann das so was kommen
Es spricht nichts dagegen, so eine TM in einer Reduktion zu verwenden. Allerdings wird die Reduktionsfunktion “f(x) = für alle x, M ist eine TM die nie hält” wohl eher selten zum Ziel führen.