Reduktionen sind zu schonen…
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.
Klausur WS2011/12 - Aufgabe 2b - Reduktion
Guten Morgen,
Es geht um die Aufgabe2b des WS2011/12.
Link zum Braindump: https://fsi.informatik.uni-erlangen.de/dw/_media/pruefungen/bachelor/bfs-braindump-2012-04.pdf
L = {y#z | M ist DTM die für die Eingabe y in {0,1}* und die Eingabe z in {0,1}* nicht hält}
Ich Frage mich, wie ich meine TM M_schlau hinschreiben soll, und wo y und z in dieser Maschine auftauchen. Idee bislang:
f(x) =
{<M_schlau_w>0#1 falls x = w}
{ 0 Sonst}
Berechenbar durch Syntaxanalyse, und total durch das “Sonst”.
Das mit 0#1 habe ich mal so “festgelegt”, inspiriert von einer Übungsaufgabe, in der die TM für nur k-viele-Eingaben halten darf.
Unsicher bin ich mir nun hier:
Programmiere M_schlau_w:
- Die Eingabe sei x
- Starte M mit w
- Falls x == 0 oder x == 1: Gehe in Endlosschleife
- Halte
//Hier kommt noch die Begründung:
Ist das so richtig, oder muss ich y und z noch übergeben?
Um Hilfe dankbar 
also ich finde die Aufgabe iwie komisch.
Es heißt ja: M ist DTM die für die Eingabe y in {0,1}* und die Eingabe z in {0,1}* nicht hält
=> daraus kann man aber eigentlich nicht folgern ob sie für die restlichen Eingaben hält.
Das wiederum würde heißen, dass deine Maschine bei x nicht aus H zurückgeben würde das es in Sprache L ist, da:
M gestartet mit w hält nicht
=> M_schlau hält nicht für 0 oder 1
=> f(x) aus L => Widerspruch.
Einfacher aus meiner Sicht wäre hier eine Reduktion mit dem Komplement von H:
Eingabe sei z
Falls x == 0 oder x == 1 Starte M mit w
sonst halte
x aus H’ => M gestartet mit w hält nicht => aus L
x nicht aus H’ => M gestartet mit w hält => nicht aus L
Angenommen, man kann folgern das die Maschine für alle anderen Eingaben hält geht deine Reduktion natürlich schon, denk ich
Wobei ich mir auch nicht sicher bin ob man nicht besser y und z als Eingabe trennt
[quote=[hedgehogs dilemma = 42]]
also ich finde die Aufgabe iwie komisch.
Es heißt ja: M ist DTM die für die Eingabe y in {0,1}* und die Eingabe z in {0,1}* nicht hält
=> daraus kann man aber eigentlich nicht folgern ob sie für die restlichen Eingaben hält.
[/quote]
Da hast du natürlich Recht. Diesen wichtigen Punkt habe ich vollkommen übersehen. Es kann ja auch für andere Eingaben halten/nicht halten.
[quote=[hedgehogs dilemma = 42]]
Einfacher aus meiner Sicht wäre hier eine Reduktion mit dem Komplement von H:
Eingabe sei z
Falls x == 0 oder x == 1 Starte M mit w
sonst halte
x aus H’ => M gestartet mit w hält nicht => aus L
x nicht aus H’ => M gestartet mit w hält => nicht aus L
[/quote]
Stimmt, ist natürlich besser. Das bezieht sich direkt auf L, und macht keine Aussagen über die anderen Eingaben. Geschickt.
[quote=[hedgehogs dilemma = 42]]
Angenommen, man kann folgern das die Maschine für alle anderen Eingaben hält geht deine Reduktion natürlich schon, denk ich
Wobei ich mir auch nicht sicher bin ob man nicht besser y und z als Eingabe trennt
[/quote]
Und ob man die 0 und 1 so in seiner TM verwenden darf. Falls das jemand sicher weiß, bin um Antworten dankbar.
Natürlich darfst du das 
Hoffe mal, dass mir keiner meine Fadennekrophilie uebel nimmt, aber dieses Thema koennte ja zur Zeit den ein oder anderen auch interessieren.
Ich haette auch [o]H[/o] auf L reduziert, bin mir aber nicht ganz sicher ob das wie folgt passt:
Zu zeigen: [o]H[/o] <= L, also: x ∈ [o]H[/o] <=> f(x) ∈ L
T_w:
Starte M mit w
Halte
T_2:
Halte nicht (Endlosschleife)
<T_<M>w>0x0 , falls x = <M>w
f(x) = {
<T_2> , sonst
x ∈ [o]H[/o]:
- x = w, M gestartet mit w haelt nicht
→ f(x) = <T_w>0#0 ∈ L - x != w
→ f(x) = <T_2> (haelt nicht) ∈ L
x ∉ [o]H[/o]:
- x = w, M gestartet mit w haelt
→ f(x) = <T_w>0#0 ∉ L
→ [o]H[/o] laesst sich mit f zu L reduzieren.
Waere huebsch wenn jmd. was konstruktive sagen koennte.
@feni:
meines Erachtens geht das so nicht, denn:
Wenn x ∈ Komplement von H, dann soll ja f(x) ∈ L sein. f(x) ist aber jetzt <T_w>0#0 und das ist garantiert nicht aus L, denn dann müsste diese TM ja gestartet mit 0 halten und gestartet mit 0 nicht halten. In jedem Fall muss also da was unterschiedliches stehen und die TM muss bei der ersten Eingabe auch wirklich halten.
Das zweite Problem ist: wenn x ∈ Komplement von H, dann kann x gar nicht ≠ w sein, der zweite Punkt in dieser Falluntercheidung ist damit zwar nicht falsch aber überflüssig. Dieser muss aber im Fall x ∉ Komplement von H auftauchen und f(x) darf dann auch nicht aus L sein
Übrigens ist dein “sonst”-Fall in f unabhängig davon, wie T_2 genau definiert ist, nicht in L, denn dazu stimmt das Format nicht 
(nur als Anmerkung, falls das so beabsichtigt ist, ist es ja vollkommen richtig )
Ich skizziere kurz wie ich das lösen würde:
Reduktion: H ≤ L
f(x) = { <FesteMaschine_>w#0, falls x = w
0, sonst }
FesteMaschine_:
- Eingabe ist w
- Falls w = 0: Endlosschleife
- Starte M mit w
- Halte
Ist nun x ∈ H: x = w ∧ M gest. mit w hält ⇒ f(x) = <FesteMaschine_>w#0 ∧ M gest. mit w hält ⇒ FesteMaschine_ hält für 1. Eingabe (w) und für 2. Eingabe nicht (0) ⇒ f(x) ∈ L
Ist x ∉ H:
Fall 1: x = w ∧ M gest. mit w hält nicht ⇒ f(x) = <FesteMaschine_>w#0 ∧ M gest. mit w hält nicht ⇒ FesteMaschine_ hält weder für 1. Eingabe noch für 2. Eingabe ⇒ f(x) ∉ L
Fall 2: x ≠ w ⇒ f(x) = 0 ⇒ f(x) ∉ L (da 0 mangels korrekter Form gar nicht aus L sein kann)
Wenn man das ganze statt mit H mit dem Komplement von H machen möchte, braucht man prinzipiell nur in der Reduktionsfunktion das w und die 0 tauschen und die FesteMaschine ganz leicht anpassen.
Um das mal festzuhalten:
Da hab ich gleich mehrere Fragen:
- Kann man das machen, dass man sagt man uebergibt der TM erst die Eingabe und dann die andere Eingabe? Ich hab mir das eher so vorgestellt, dass bei „<FesteMaschine_>w#0“ die Eingabe eben „w#0“ ist.
- Wenn herleitest, dass [quote]f(x) ∈ L[/quote] weil [quote]FesteMaschine_ hält für 1. Eingabe (w) und für 2. Eingabe nicht (0)[/quote] dann ist das doch ein Widerspruch zu L, oder? schlieszlich wird hier nicht ausgeschlossen, dass w nicht aus {0,1}* ist
→ die TM wuerde fuer die Eingabe x#y mit x, y ∈ {0,1}* halten
Kann aber auch sein, dass ich gerade vollends verwirrt bin :rolleyes:
Und nun habe ich gerade festgestellt, dass ich die Aufgabenstellung falsch gelesen habe - nämlich so, dass M für y halten soll aber nicht für z. Gut, dass du nochmal die Aufgabe zitiert hast :D.
Das folgende bezieht sich also nur mehr teilweise auf deine Fragen.
Zum Format: In L sind beide Eingaben enthalten, aber die Maschine in L erhält nur eine Eingabe. So wie es beschrieben ist, sollen y und z nur spezielle Eingaben sein, M kann aber auch andere verarbeiten.
Zu deiner zweiten Frage:
Da hast du Recht, da hab ich nicht aufgepasst. Das Problem umgeht man recht schnell, indem man f umschreibt zu:
f(x) = { <FesteMaschine_>0w#epsilon, falls x = w,
0, sonst }
und: FesteMaschine_:
- Eingabe ist w
- Falls w = epsilon: Endlosschleife
- Sei w’ def. als w ohne erstem Zeichen; Starte M mit w’
- Halte