Ich gehe jetzt mal nur auf die erste Frage ein. Da sollten genug Lücken zu stopfen sein um sich eine gute Weile mit zu beschäftigen. Und wenn das verstanden ist, dann nehme ich an werden die anderen einfacher.
Das „Kleiner-gleich“, also die Reduzierbarkeitsrelation sagt leider das Gegenteil aus. Also A ≤ B bedeutet „A ist reduzierbar (sprich lösbar durch) B“, bedeutet also wer B lösen kann, kann auch A lösen. Psychisch tritt man da gerne in die sprachliche Falle, dass „A reduziert auf B“ den Anschein gibt, dass B kleiner ist, aber es geht hier um die Komplexität, also wenn ein Problem durch ein anderes gelöst wird, dann ist es selbst ja weniger komplex.
(Das soll nicht heißen, dass man Min-10 nicht auf das Halteproblem reduzieren kann, dann wären eben beide Probleme „gleichschwer“)
Wir wollen hier also das Halteproblem reduzieren auf das Min-10 Problem. Die Aussage ist „Wer Min-10 lösen kann, der hat schon das Geheimnis für das Halteproblem geknackt.“ H ≤ Min10. Wir suchen eine totale, berechenbare Funktion f, die das Halteproblem also in das Min10 Problem überführt. Und es soll gelten, dass wir die Antwort nach der Übersetzung auch beim ursprünglichen Problem benutzen können. Das ist was mit x ∈ H <=> f(x) ∈ Min10 gemeint ist.
Die richtigere Formulierung wäre eigentlich „A ist nicht schwerer als B“. Wir übersetzen ein A Problem in ein B Problem, lösen das B Problem, und geben die gleiche Antwort für das A Problem.
Natürlich muss ich auch beweisen, dass jede Akzeptanz im Fall B auch Akzeptanz im Fall A bedeuten würde, und umgekehrt, dass jede nicht-Akzeptanz im Fall B auch nicht-Akzeptanz im Fall A impliziert.
Nehmen wir uns das Beispiel doch mal her.
Das gruselige Halteproblem soll nicht schwerer sein als das Min10 Problem, von dem ich bis jetzt noch nie etwas gehört habe? Kann denn eine Lösung für das Min10 Problem zu einer Lösung für das Halteproblem führen?
Das trainierte Informatikgehirn weiß wonach es Ausschau halten muss. Alles ins Extreme führen. Randfälle betrachten.
Wir nehmen jetzt mal an, ich kann für jede TM sagen, ob sie für mindestens 10 Eingaben hält. Das gilt dann für jede Art von TM! Auch für TMs, die die Eingabe verwerfen oder ignorieren und gemütlich ihren eigenen Code ausführen. Man denke da an Eingabemasken, die es eigentlich nicht interessiert, was du angekreuzt hast.
Was also, wenn ich aus meiner Halteproblem TM eine neue bastele?
Das Halteproblem ist folgendermaßen definiert: Gegeben Turingmaschine M und Eingabe w, M hält für w.
Das bedeutet wenn etwas keine Turingmaschinenkodierung gefolgt von Eingabe ist, dann ist es auch Element des Halteproblems. Das ist nicht ganz unwichtig.
Wir müssen ein f basteln, sodass x ∈ H <=> f(x) ∈ Min10.
Nehmen wir jetzt 3 Fälle für unser x her:
- Eine TM M und eine Eingabe w, und M hält tatsächlich für w, also ist x = M,w ∈ H.
- Eine TM M’ und eine Eingabe w’, und M’ hält nicht für w’, also x = M,w ∉ H.
- Ein Input g, der keine Turingmaschine gefolgt von Eingabe ist (quasi ein Syntax Error). Hier wieder x = g ∉ H.
Für den ersten Fall soll f(x) ∈ Min10, für die anderen beiden Fälle nicht.
Ob etwas ein Syntax Error ist, also keine Turingmaschine gefolgt von Eingabe, lässt sich in Polynomialzeit entscheiden. Das ist also berechenbar.
Alle solche Eingaben wollen wir auch für unsere Übersetzung ins Nirvana katapultieren.
Zur Erinnerung, das Ziel ist, bei jeder Eingabe x, die nicht in H ist, auch etwas in f(x) auszuspucken, das nicht in Min10 ist.
Also lege ich fest, f(x) für x nicht von der Form M,w soll ergeben „0“. Das ist keine Turingmaschine, also garantiert auch nicht in Min10.
Jetzt nehme ich eine Turingmaschine M und Eingabe w her. Sagen wir ich bastele mir eine neue Turingmaschine. Es existiert ja eine sogenannte universelle Turingmaschine, die andere Turingmaschinen ausführen kann. Und eine solche werden wir benutzen. Je nach x = M,w basteln wir uns also eine Turingmaschine M’_⟨M,w⟩, die die wir der Ausgabe f(x) zuordnen.
Wenn ich M’_⟨M,w⟩ jetzt mit einer Eingabe w’ starte, dann soll M’_⟨M,w⟩ folgendes tun:
- Starte M mit w.
- Fertig. Halte akzeptierend.
Hä? Und was ist mit der Eingabe w’? Die ist uns egal. Zeit wieder rauszuzoomen. Was passiert jetzt mit unserer Funktion f?
Wir bekommen ein x. Wenn dieses x nicht von der Form M,w ist, dann bekommen wir auch keine Turingmaschine als Ausgabe f(x), damit ist trivialerweise f(x) ∉ Min10.
Jetzt zu dem Fall, dass x = M,w. Hier wie oben schon beschrieben gibt es zwei Fälle:
-
Was passiert wenn M,w ∈ H?
Dann hält M gestartet mit w. Das bedeutet für M’_⟨M,w⟩, dass es für jede Eingabe w’ akzeptierend hält. Ihm ist ja egal welches w’ er bekommt, da wird nur stur M mit w ausgeführt, und weil das irgendwann fertig ist (M,w ist in H, somit kann ich mich nicht in einer Dauerschleife verfangen), wird haltend akzeptiert.
Unser f(x) = M’_⟨M,w⟩ ist nun eine Turingmaschine, die für alle Eingaben hält. Also auch für mindestens 10 verschiedene. f(x) ∈ Min10.
-
Was passiert wenn M,w ∉ H?
Dann hält M gestartet mit w nicht. Da ist eine Dauerschleife, also verfängt sich auch M’_⟨M,w⟩ in dieser und hält nicht akzeptierend. Nie. Da kann man an w’ rumspielen wie man will, M’_⟨M,w⟩ interessiert das nicht. In diesem Fall hält f(x) = M’_⟨M,w⟩ also nie akzeptierend. Also ist auch kein Wort in seiner Sprache. Bedeutet also nichtmal 10 Wörter. Eher 0. f(x) ∉ Min10.
Ich betone hierbei nochmal: f(x) macht im Fall „x von der Form M,w“ nicht zwei verschiedene Sachen, er baut immer den gleichen Automaten nach Rezept, aber eben die Zutat M,w hat in einem Fall die Eigenschaft in H zu sein, und im anderen Fall eben nicht. Und deswegen bekommen wir auch zwei verschiedene Verhalten.
Unser f(x) ist berechenbar, weil diese Konstruktion der universellen Turingmaschine ja möglich ist, der Syntaxcheck auch. Und die f ist total, was einfach bedeutet, dass wir jede Möglichkeit für x abgedeckt haben. Die Funktion wäre nicht total, wenn ich nur Fälle betrachtet hätte, in denen x von der Form M,w ist. Weil was wenn nicht? Dann wäre die Funktion auf solchen anderen x nicht definiert und somit die Funktion nicht auf allen möglichen Eingaben definiert. Deswegen dieser Fall mit der Mülleingabe g, bei der f(g) = „0“.
Für mindestens 10 Eingaben halten ist auch ein bisschen ein red herring. Die Zahl 10 hätte auch die Zahl 58 sein können, die Konstruktion bleibt gleich.
Das wäre ein Musteraufbau für eine Reduktionsaufgabe. Ich hoffe es nützt zumindest etwas. Du kannst ja im selben Stil versuchen andere Reduktionen durchzuführen, beim selbst probieren kommen sehr schnell die Wissenslücken zum Vorschein.
Das zu lesen hat mich ein bisschen erschreckt, und sehr glücklich gemacht. Freut mich dass das Beispiel so gut im Kopf geblieben ist.
Gruß
Feyven
hier noch eine frage