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.
Sinn der Syntaxanalyse bei Reduktionen
Reduktionen bilden Wörter aus einer Sprache in eine andere ab, und behalten dabei (im Kontext von Reduktionen mit Turing Machinen) Eigenschaften hinsichtlich des Wortproblems bei. Wieso ist es aber notwendig das die Form der Funktion f: {0, 1} → {0, 1} von und auf ganz {0, 1} abbilden, anstatt “lediglich” von der Menge der Turing Maschinen oder auf die gleiche. Sinngemäß scheint sich doch dabei nichts zu verändern, oder weshalb ist die Syntaxanalyse auf (bspw. [m]w[/m] bei der Halteproblem->init. Halteproblem Reduktion) relevant per se?
Ich glaube nicht das die Antwort sein kann [m]w[/m] muss eine Zeichenkette sein, deswegen ist ganz {0, 1} notwendig, da eine Reduktionsfunktion ja auch einfach von der Menge der Tupel von TMs und Eingaben auf etwas anderes (abhängig von der Reduktion) abbilden könnte.
Ist dieses also nur Konvention, oder hängt das vll mit dem zusammen dass bei unseren Reduktionen “starte mit” eine Universelle TM impliziert, die selbst nur Zeichenketten/Band eingaben annehmen kann? Wenn ja, würde die Syntaxanalyse wegfallen können wenn jede Natürliche Zahl eine Gödelnummer wäre, oder allgemein wenn ein Berechnungsmodell benutzt werden würde wo nur syntaktisch korrekte Programme konstruiert werden können?
(Hab ich meine Frage selbst beantwortet?)
Ein wesentlicher Punkt, warum man Reduktionen A <= B überhaupt betreibt, ist, um Folgendes zu zeigen: Wenn B entscheidbar ist, so ist auch A entscheidbar.
Warum folgt das aus A <= B? Siehe Satz aus der VL oder hier: wir können einen Entscheider für A wie folgt bauen:
- Lies Eingabe w
- Wende die Reduktionsfunktion anwenden (beachte: diese war total berechenbar!)
- Wende den Entscheider von B an (B entscheidbar => es ex. eine TM, die entscheidet, ob die jeweilige Eingabe zu B gehört.) und übernimm sein Ergebnis.
Wäre die Reduktionsfunktion [m]f: {0,1}* → {0,1}*[/m] nicht berechenbar, so könnten wir Schritt 2 nicht tun, denn dann gäbe es keine TM dafür. Wäre sie nicht total, könnten wir sie nicht auf beliebige Eingaben w in Schritt 2 anwenden.
Vielleicht hattest du Folgendes im Kopf für den Entscheider. Wir könnten eine entscheidbare Teilmenge S von A wählen und nennen diese die “syntaktisch korrekte Teilmenge”. Nun definieren wir die Reduktionsfunktion [m]f: A → {0,1}*[/m]. Den Entscheider bauen wir wie folgt:
- Lies Eingabe w
- Entscheide, ob w in A (d.h. syntaktisch korrekt) ist. Falls nein, halte verwerfend.
- Falls ja, wende die Reduktionsfunktion an. (beachte: diese war auf A definiert und berechenbar)
- Wende den Entscheider von B an und übernimm sein Ergebnis.
Das geht genauso! Nun hast du den Syntaxcheck aber nur verlagert und musst beweisen, dass S entscheidbar ist bzw. dafür einen Entscheider angeben.
PS: Wenn du [ m ] als Codetag benutzt, werden Kleene’sche Sterne richtig gesetzt.
1 „Gefällt mir“
[quote=Marcel[Inf]]
Vielleicht hattest du Folgendes im Kopf für den Entscheider. Wir könnten eine entscheidbare Teilmenge S von A wählen und nennen diese die “syntaktisch korrekte Teilmenge”. Nun definieren wir die Reduktionsfunktion [m]f: A → {0,1}*[/m]. Den Entscheider bauen wir wie folgt:
- Lies Eingabe w
- Entscheide, ob w in A (d.h. syntaktisch korrekt) ist. Falls nein, halte verwerfend.
- Falls ja, wende die Reduktionsfunktion an. (beachte: diese war auf A definiert und berechenbar)
- Wende den Entscheider von B an und übernimm sein Ergebnis.
Das geht genauso! Nun hast du den Syntaxcheck aber nur verlagert und musst beweisen, dass S entscheidbar ist bzw. dafür einen Entscheider angeben.
[/quote]
Ich habe mir gedacht das es in die Richtug geht, aber dank deinem letztem Satz lässt glaube ich jetzt zu verstehen was mich verwirrt hat, weil ich das mit der Totalen Berechenbarkeit der Reduktionsfunktion vergessen hatte. Danke für den Hinweis!
Wenn ich Ihre Frage korrekt interpretiere, geht es darum, warum es im Spiegeleibild auf der linken Seite für jede Zeichenfolge w ϵ {0,1}* ein Bild f(w) auf der rechten Seite geben muß, also gefordert ist, daß f total ist.
Es geht dabei um die benötigte Äquivalenz bei L[sub]1[/sub] ≤ L[sub]2[/sub]: w ϵ L[sub]1[/sub] ⇔ f(w) ϵ L[sub]2[/sub]. Die Totalität von f liefert erst die Richtung „⇐“.
Die totalität kann ich vollkommen nachvollziehen. Meine Frage ging auf den Datentyp/Domaine der Reduktionsfunktion hinaus. Also wie der Marcel es formuliert hat, wenn „S“ die Menge der syntaktisch-validen TMs ist, wieso man nicht von „S → S“ abbilden kann (oder geeignete deviationen: (S, w) → S, S → (S, w) , …).
Ich denke, die Codomain der Reduktionsfunktion kann eine beliebige Teilmenge von [m]{0, 1}^[/m] sein. (Insbesondere induziert jede Funktion g: A → B implizit auch eine Funktion g’: A → B’, wenn B’ eine [ggf. unechte] Obermenge von B ist.)
D.h. für die Reduktion von der VL könntest du auch ein [m]f: {0, 1}^ → S[/m] benutzen, wobei die Reduktionsfunktion dann das f’ ist, dessen Codomain auf [m]{0, 1}^*[/m] erweitert wurde. (Ich merke mal an, dass viele Leute gar nicht so formal sind, sondern einfach „g: A → B ist auch eine Funktion g: A → B’“ schreiben. Sobald du aber nicht mehr von Funktionen auf Mengen, sondern von allgemeinen Morphismen in Kategorien redest, empfehle ich, wieder pedantisch zu sein ;))
Dass die Domain mindestens eine unechte Obermenge von [m]{0, 1}^*[/m] sein muss, wurde oben bereits erwähnt:
Ist dein Problem vielleicht eher, dass du dieses „f(x) = 0 falls x != <M, w> für ein M und für ein w“ und „f(x) = … falls x = <M, w> für ein M und für ei nw“ als Boilerplate empfindest? Falls ja, dann kannst du das klar auch in der Theorie kosmetisch entfernen (siehe mein Beitrag oben mit S), aber ich bin mir nicht sicher, ob es das konzeptionell einfacher macht.
Aha.
Diese Thematik hatte ich auch in der Vorlesung zu Beginn der Behandlung der Reduktionen anhand eines Negativ-Beispiels beleuchtet, als ich eine “Reduktionsfunktion” angegeben hatte, die nicht berechenbar ist. Und wäre die Berechenbarkeit nicht Teil der Definition, wäre nämlich alles auf alles reduzierbar, solange die beteiligten Sprachen nicht Ø und Σ* sind.