Reduktion von einem Problem P1 auf das allgemeine Halteproblem

Question

ich studiere angewandte Informatik und bereite mich aktuell auf eine Klausur vor, die im Bereich der theoretischen Informatik angesiedelt ist. Eigentlich bin ich recht gut vorbereitet, allerdings habe ich trotz intensiver Bemühungen immer noch Probleme mit dem Thema Reduktionen. Das grundlegende Prinzip ist mir bewusst, allerdings bin ich häufig nicht in der Lage, eine korrekte Vorverarbeitungsfunktion zu finden, so auch bei dem folgenden Problem:

Gegeben ist ein Problem P = {w1#w2#x | wenn die Turingmaschine Mw1 auf x hält dann hält auch Mw2 auf x}

Ich wollte dieses Problem auf das allgemeine Halteproblem H = {w#x | Mw hält auf der Eingabe x} reduzieren. Folgende Vorverarbeitungsfunktion wollte ich für die Reduktion verwenden: f(w#x) = w#w#x.

Aus der Aufgabenstellung geht jedoch hervor, dass diese Vorverarbeitungsfunktion nicht korrekt ist, weil diese Vorverarbeitungsfunktion dort angegeben ist und man erläutern soll, was daran falsch sein soll.

Ich begreife nicht, was an der Vorverarbeitungsfunktion falsch sein könnte, denn das Problem P nimmt zwei Kodierungen und eine Eingabe entgegen. Eine Kodierung ist für Mw1 und die andere für Mw2, außerdem arbeiten beide mit der gleichen Eingabe x. Wenn wir nun Mw1 und Mw2 die Kodierung des Halteproblems übergeben und außerdem noch die Eingabe x des Halteproblems, dann sollte sich damit doch das Halteproblem lösen lassen, von dem wir allerdings wissen, dass es unentscheidbar ist und somit würde daraus resultieren, dass auch das Problem P unentscheidbar ist.

Beide Maschinen aus dem Problem P sollten sich doch nun gleich verhalten, weil beide mit der gleichen Kodierung als auch mit der gleichen Eingabe arbeiten, dementsprechend müsste doch Mw1 auf der Eingabe x halten, wenn auch Mw2 auf der Eingabe x hält. Gleichzeitig sollte auch gelten, dass wenn Mw1 nicht auf der Eingabe x hält, dass dann auch Mw2 nicht auf der Eingabe x hält.

Beide Maschinen müssten sich nach meinem Verständnis nun gleich verhalten, weil beide mit der gleichen Kodierung und Eingabe arbeiten. Da ich davon ausging, dass diese Vorverarbeitungsfunktion korrekt sein müsste, fällt mir leider auch keine andere Vorverarbeitungsfunktion ein, die ich für diese Reduktion verwenden könnte.

Ich wäre erfreut, wenn mir jemand einen Ratschlag geben könnte, warum diese Vorverarbeitungsfunktion nicht korrekt sein soll, ich denke, dann komme ich auch auf eine korrekte Vorverarbeitungsfunktion für die Reduktion.

Nette Grüße

BinaryDigit

Answer 1

f(w#x) = w#w#x

Der Satz

        "Wenn Mw auf x hält, dann hält Mw auf x"

ist eine Tautologie. Also ist w#w#x ∈ P unabhängig davon ob w#x ∈ H oder w#x ∉ H ist.

Ich wollte dieses Problem auf das allgemeine Halteproblem H ... reduzieren.

Das möchtest du eigentlich nicht. Du möchtest H auf P reduzieren und damit zeigen, dass H in dem Sinne einfacher als P ist, dass wenn du P lösen könntest, auch das vermeintlich einfachere Problem H lösen könntest.

Verwende dazu

        f(w#x) = h#w#x

wobei h eine Turingmaschine kodiert, die auf jeder Eingabe hält.

Comments

Hallo Oswald,

erst mal vielen Dank für deine Antwort. Du hast natürlich recht damit, dass ich H auf P reduzieren wollte, um zu zeigen, dass man mittels P dann auch H lösen könnte, wodurch bewiesen wäre, dass Problem P unentscheidbar ist, weil auch H unentscheidbar ist.

Deine Antwort hat mir wirklich weitergeholfen. Wenn ich das jetzt richtig verstehe, dann nehmen wir sozusagen die erste Maschine, die auf w1 arbeitet heraus, indem wir diese immer terminieren lassen. Dadurch bleibt dann sozusagen nur noch die Maschine übrig, die auf die Kodierung w2 arbeitet, was dann auch mit dem Problem H übereinstimmt, weil diese ebenfalls nur auf einer Kodierung agiert.

Ich hoffe, dass ich nun auch mit anderen Aufgabenstellung der gleichen Art besser klarkomme. Nochmals vielen Dank und noch einen schönen Tag.

Nette Grüße

BinaryDigit

---

Wenn ich das jetzt richtig verstehe

Prüfe das indem du dir überlegst, warum folgende Funktionen ungeeignet sind:

1. f(w#x) = w#h#x wobei h eine Turingmaschine kodiert, die auf jeder Eingabe hält.
2. f(w#x) = n#w#x wobei n eine Turingmaschine kodiert, die auf x nicht hält.
   
3. f(w#x) = w#n#x wobei n eine Turingmaschine kodiert, die auf x nicht hält.
   

---

Ich habe die Klausur zwar bereits geschrieben und warte aktuell auf die Ergebnisse, aber um das zu vervollständigen, versuche ich die folgenden Fragen trotzdem zu beantworten:

1) In diesem Fall würde Ja (1) ausgegeben werden, wenn H auf x hält, denn Mw1 hält auf der Eingabe x, wenn auch Mw2 auf der Eingabe x hält, was passend wäre. Der andere Fall ist jedoch nicht passend, hier müsste Nein (0) ausgegeben werden, wenn H nicht auf x hält, dementsprechend müsste Mw1 nicht auf x terminieren, wenn auch Mw2 nicht auf x terminiert, jedoch kann immer nur herauskommen, dass Mw1 nicht auf x terminiert und Mw2 auf x terminiert, was dementsprechend keine passende Vorverarbeitungsfunktion darstellt.

2) In diesem Fall würde Nein (0) ausgegeben werden, wenn H nicht auf x hält, denn dann terminiert Mw1 als auch Mw2 nicht auf x, was passend wäre. Der andere Fall ist aber dann wiederum nicht passend, hier müsste Ja (1) ausgegeben werden, wenn H auf x hält, dementsprechend müsste Mw1 als auch Mw2 auf x terminieren, was aber niemals passieren kann, da Mw2 niemals auf x terminiert und somit ist dieser Fall unerreichbar und die Vorverarbeitungsfunktion kann nicht korrekt sein.

3) Dieser Fall ist im Prinzip der Gleiche, wie bei Fall 2. Es würde Nein (0) ausgegeben werden, wenn H nicht auf der Eingabe x terminiert, denn dann terminiert Mw1 als auch Mw2 nicht auf x, was wiederum passend wäre. Der andere Fall wäre allerdings wiederum unerreichbar, da Mw2 niemals auf der Eingabe x terminiert, kann es nicht zu der Konstellation kommen, dass Mw1 als auch Mw2 auf x halten, was aber die Bedingungen für die Ausgabe Ja (1) darstellt, die immer dann ausgegeben werden müsste, wenn H auf x hält.

Ich hoffe, dass ich meinen Gedankengang einigermaßen verständlich darstellen konnte und bedanke mich noch mal für deine Hilfe.