Wie kann man so Aufgabe lösen (Reduktion)?
Hallo, ich verstehe die Konzept auf Reduktion, und auch Turing machine. aber ich weiss nich wie man mit so Aufgaben umgehen muss.
2 Antworten
Soweit ich mich an die in grauen Vorzeiten gelernte Berechenbarkeitstheorie richtig erinnere, mußt du wenn H_1 <= H_2 sein soll zeigen können, dass die Maschine H_2 den Spezialfall H_1 enthält (auf ihn reduziert werden kann), d.h. auch zur Berechnung von H_1 eingesetzt werden kann. Mit einer Reduktion auf das (spezielle) Halteproblem wird dann gezeigt, dass eine Maschine wie in der Behauptung nicht konstruiert werden kann.
Beispiel: in der ersten Aufgabe wird H_T auf das spezielle Halteproblem reduziert. Demzufolge gibt es keine Turingmaschine, die H_T entscheiden kann.
Ich habe das ganze mit dem Ansatz über Programmiersprachen, wie er im Buch von Kfoury, Moll und Arbib: "A Programming Approach to Computability" gewählt wird gelernt. Der Ansatz über Turingmaschinen ist aber isomorph.
Meine Antwort ähnelt der anderen, versucht aber allgemeiner zu sein.
Nehmen wir an, dass du eine Funktion F hast. F(x) = x*x dann ist G(x,y)=x*y einfach "mächtiger", weil du damit mehr rechnen kannst als x*x aber auch x*x (G(x,y) wobei x=x und y=x equivalent F(x)). F(x) kann also nicht mächtiger sein als G(x,y). Das mit größergleich darzustellen finde ich widerlich aber k.
Wenn du also entscheiden möchtest ob etwas bei beliebiger Eingabe hält oder bei beliebiger Eingabe nicht hält, dann musst du zeigen, dass es bei jeder Eingabe hält oder nicht hält; also das Halteproblem für alle Eingaben lösen.
for(all Eingaben){
doHalteProblem(Eingabe);
}
Das kann kaum einfacher sein als:
doHalteProblem(Eingabe); da es für jede Eingabe einmal aufgerufen wird.
Für die obere Aufgabe kannst du es dir also "einfach" machen und überlegen:
Wo benötigt das lösen dieses Problems die Lösung des Halteproblems?
Bei anderen Problemen ist das schwieriger, darauf gehe ich jetzt aber nicht näher ein, da es sonst zu lang wird.