Aufgabe 1
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.
Braindump 2010-04
Bin mir bei den folgenden 4 Aussagen unsicher, ob richtig oder falsch. Vielleicht habt ihr eine Idee?
Aussage 1:
Alle Sprachen in NP sind entscheidbar.
Antwort: Richtig, denn alle Sprachen in NP sind per Def. mit einer nichtdet. TM in Polyzeit entscheidbar.
Aussage 2:
L_1 und L_2 unentscheidbar => L_1 ∆ L_2 auch unentscheidbar. [ L_1 ∆ L_2 := (L_1 ∪ L_2) - (L_1 ∩ L_2) ]
Antwort: Falsch, L_1 := H; L_2 := Kompl(H); => H ∆ Kompl(H) = {0,1}* - {} = {0,1}* => entscheidbar
Aussage 3:
Die Sprache L = {⟨M⟩ | M hält mindestens für die Eingaben w1 und w2; w1,w2 ∈ Σ*, w1 ≠ w2} ist nicht rekursiv aufzählbar.
Antwort: Ich glaube es ist falsch, denn es müsste dann Kompl(H) ≤ L sein und das “min.” macht jedes mal meine Reduktion kaputt, daher nehme ich an das es nicht geht. (Genauere Begründung?)
Aussage 4: (korrigiert)
Wenn L regulär ist, besitzt L die kontextfreie Pumpeigenschaft.
Antwort: Falsch, da regulär echte Teilmenge von Kontextfrei => L kann die kf. PE. haben muss aber nicht.
Richtig, da reg. Sprache auch kf. => L hat also auch die kf. PE
Ist bei mir jetzt etwas her aber:
War das mit Pump-Eigenschaft nicht immer, dass alle regulaeren/kontextfreien sprachen die jeweilige Pumpeigenschaft erfuellen es aber weitere Sprachen gibt die zwar nicht regulaer/kontextfrei sind aber trotzdem die pumpeigenschaft erfuellen?
In dem Fall:
- Alle Regulaeren Sprachen sind kontextfrei
- Alle kontextfreien Sprachen erfuellen die Pumpeigenschaft fuer kontextfreie Sprachen
- Alle regulaeren Sprachen erfuellen die Pumpeigenschaft fuer kontextfreie Sprachen
1 „Gefällt mir“
Müssten beide so stimmen.
Mit Aussage 3 kann ich grade nichts genaues anfangen, sind diese Wörter w1,w2 vorgegeben? Oder steht da noch ein Existenzquantor?
Zur 3:
Eine universale TM die einfach M mit w1 und dann mit w2 simuliert und ggf. hält müsste doch ein rekursiver Aufzähler für L sein, ergo L rekursiv aufzählbar, oder?
Zur 4:
Ist es nicht so? Regulär echte Teilmenge von kontextfrei => jede reguläre Sprache ist kontextfrei => (Satz 3.33) jede reguläre Sprache hat die kontextfreie Pumpeigenschaft.
Eine Frage noch zur 2:
Ist - das Gleiche wie ? Wenn nein, wo liegt der Unterschied?
Zu 4.:
L is regulär => L hat die reg. P.E.
Steht sonst nichts dabei.
Zur 4: Stimmt, eine reg. Sprache müsste auch kf. sein und damit auch die kf. PE. haben. Korrigiere ich mal.
Falls die Formulierung heißen soll: „Hält für mindestens zwei unterschiedliche Eingaben“, ist das nicht ganz so einfach, aber trotzdem immer noch rekursiv aufzählbar.
Falls w1 und w2 fest vorgegebene Wörter waren ist so einfach 
Ich habs als Differenz also wie \ interpretiert.
Dazu habe ich noch eine Frage: Wie lautet die Def. das eine TM ein rek. Aufzähler für eine Sprache L ist?
Wenn ich w1 und w2 (w1 ≠ w2) mit M auf einer univ. TM ausführe, dann muss diese ja halten damit in der Sprache liegt, für andere Eingaben ist es egal ob gehalten wird. Was davon sagt mir nun das diese univ. TM der rek. Aufzähler ist?
Eine Sprache ist genau dann rek. aufzählbar, wenn es eine det. 1-Band-TM gibt, die L akzeptiert.
Deine Sprache ist ja die Menge aller TM, die mit zwei bestimmten Eingaben halten.
eine TM, die L akzeptiert, bekommt also eine andere TM übergeben, die getestet werden soll. Deine TM M ließt also die die Eingabe(was eine TM M’ ist) und führt M’ mit w1 und w2 aus. Hält M’ für beide Eingaben, hält auch M akzeptierend. Damit akzeptiert M die Sprache L und L ist rekursiv aufzählbar.
Weil M offensichtlich in der Lage ist, eine andere TM, die sie als Eingabe übergeben bekommt, zu simulieren, ist es per Definition eine universelle TM.
Wie würdest du das machen? Gleichzeitig parallel ausführen war mein erster Gedanke. Allerdings ist die Eingabelänge ja nicht beschränkt. Daher denke ich nicht, dass man mit einer „unendlich parallelen“ Turing-Maschine, die gleichzeitig alle Wörter durchprobiert argumentieren kann ;).
Du musst ja nicht mit allen auf einmal anfangen :D.
Die möglichen Eingaben sind ja abzählbar (endliches ∑ vorausgesetzt). Also simulierst du parallel pro simuliertem Schritt eine Eingabe mehr.
Danke für die Erklärung!
∑ ist zwar endlich aber eine Eingabe für M ist ∑* und das ist nicht abzählbar. Um nun zu zeigen, dass M mit zwei unterschiedlichen Eingaben hält, musst du die TM M mit jeder Eingabe parallel laufen lassen.
Da nun aber die Eingabe in ∑* ist, hast du unendlich viele Eingaben und müsstest somit parallel M mit allen Eingaben laufen lassen. Da aber eine TM M nur endlich viele Bänder hat, kann man nur endlich viele Eingaben gleichzeitig testen. Wenn nun keine davon hält, dann könnte es trotzdem noch 2 Eingaben geben für die M hält. Also könnte in dieser Sprache sein, aber deine TM hält. Also gibt es keinen rekursiven Aufzähler für L = {| M hält für mindestens 2 Eingaben}
Aufgabe 2 b)
Muss bei Aufgabe 2 b) eigentlich in der Beschreibung der festen Maschine ein Algorithmus zur Berechnung der Binärdarstellung angegeben werden? Oder reicht ein lapidares “Berechne bin(…)”?
Nachdem sich die richtige Antwort bereits oben eingestellt hatte, will ich hier schnell sagen:
L = {<M>| M hält für mindestens 2 Eingaben} [b]ist[/b] rekursiv aufzählbar.
bulsas Aussage
ist der Schlüssel zum Verständnis. In Aufgabe 27 auf Blatt 5 (Hardware-Software-Co-Design › Lehrstuhl für Informatik 12 ) haben wir sozusagen genau das gemacht. Für L hat man zwei verschachtelte Schleifen: eine gibt die simulierte Schrittzahl t an, die andere steuert, daß man auf den verschiedenen Eingaben x[sub]1[/sub],…,x[sub]t[/sub] jeweils t Schritte austestet.
MfG
Rolf Wanka
weiss jemand was mit dem Beisatz von Aufgabe 2b) gemeint ist
Bin mir nicht sicher ob da eine TM gemeint ist, die von einem spezifischen x die binär Darstellung von x^2 berechnet (und damit ausgibt?) ?
Wenn ich das richtig verstehe, ist also das Entscheidende, dass ich mit einer TM die als rekursiver Aufzähler für L dienen soll, systematisch alle Eingaben erzeugen (da abzählbar unendlich) und die zu prüfende TM M damit parellel mit jeder erzeugten Eingabe simulieren kann. Ist M Teil der Sprache L, so wird meine Simulation irgendwann für zwei Eingaben gehalten haben und mein rekursiver Aufzähler kann dies erkennen und selbst halten. Ansonsten laufe ich natürlich in eine Endlosschleife. Damit gilt L ist r.a.
Sehen Sie das jetzt bitte nicht (nur ;-)) als penible Klugsch…ei an: Nicht M ist Teil mögliches Element von L, sondern die Kodierung von M. Das ist ja eine der zentralen Erkenntnisse überhaupt, daß man die Baupläne wieder zu Objekten für das konkret Gebaute machen kann. Erfunden haben’s nicht die Schweizer sondern Kurt Gödel, weswegen wir ja auch als Gödelnummer bezeichnen.
Ganz weit heruntergebrochen sind (als reine Zeichenfolgen) „7“, „VII“, „|||||||“ und „sieben“ vier verschiedene Gödelnummern desselben Objekts.
Der Rest ist dann okay. 
MfG
Rolf Wanka
@manusch: Das bezieht sich auf die letzte Frage in der 1. Aber was genau M da berechnet ist glaube ich nicht so wichtig.
Danke für den Hinweis. Die Klammern fehlen natürlich und wurden fahrlässigerweise vergessen.