---

Geschrieben von Zu53 am 03.02.2019 um 03:49:

  Reduktion des allgemeinen Halteproblems auf ein Problem P1

Hallo zusammen,

ich studiere angewandte Informatik und bereite mich aktuell auf eine Klausur vor, die im Bereich der theoretischen Informatik fällt. Eigentlich bin ich recht gut vorbereitet, allerdings habe ich Probleme mit dem Thema Reduktionen und polynomielle Reduktionen. Das Prinzip ist mir zwar klar, aber ich bin häufig nicht in der Lage, eine korrekte Vorverarbeitungsfunktion zu finden, so auch bei dem folgenden Problem.

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

Ich wollte dieses Problem nun 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. Nun geht aus der Aufgabenstellung jedoch hervor, dass diese Vorverarbeitungsfunktion nicht korrekt ist, weil diese in der Aufgabenstellung bereits angegeben ist und man erläutern soll, was an dieser Vorverarbeitungsfunktion falsch sein soll.

Ich begreife nicht, was an dieser Vorverarbeitungsfunktion falsch sein soll, denn das Problem P1 nimmt zwei Kodierungen und eine Eingabe entgegen, eine für die Maschine Mw1 und eine andere für die Maschine Mw2 und für beide wird die Eingabe x verwendet. 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 P1 unentscheidbar ist.

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

Da ich davon ausgehe, 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 ist, ich denke dann komme ich auch auf eine korrekte Vorverarbeitungsfunktion für die Reduktion.

Nette Grüße

Zu53

---

Geschrieben von ed209 am 03.02.2019 um 22:08:

 

Hi

Reduktionen sind bei mir schon ein bisschen her, aber wenn ich mich recht entsinne musst du fuer die Reduktion von Problem A auf Problem B zeigen, dass b in B ist, genau dann wenn f(b) in A ist.

Nehmen wir dein f(x) und konstruieren P1':

P1' = { w#x | f(w#x) in P1 }

In deinem Fall ist f(x) immer in P1':

P1' = { w#x | wenn die Turingmaschine Mw auf x hält, dann hält Mw auf x }

Diese Bedingung ist aber immer wahr.

Entsprechend musst du ein Funktion finden, die dafür sorgt, daß f(w#x) nur dann in P1 ist, wenn w#x hält.


Gruss,
ED

---

Geschrieben von Zu53 am 04.02.2019 um 09:42:

 

Hallo ed209,

erst mal vielen Dank für deine Antwort. Ich konnte nun eine Lösung finden, mit der ich H auf das Problem P reduzieren kann, in meinen ersten Beitrag hatte ich mich zunächst mit der Reduktionsrichtung verhauen, ich hatte folgendes geschrieben: "Ich wollte dieses Problem nun auf das allgemeine Halteproblem H = {w#x | Mw hält auf der Eingabe x} reduzieren.", was nicht korrekt ist, ich meinte natürlich, dass ich das Problem H auf das Problem P1 reduzieren wollte und genau das ist eigentlich auch der Fehler bei der Vorverarbeitungsfunktion f(w#x) = w#w#x, denn das wäre eine Vorverarbeitungsfunktion, um das Problem P1 auf das Problem H zu reduzieren.

Eine korrekte Vorverarbeitungsfunktion wäre die folgende: f(w#x) = h#w#x, wobei h eine Turingmaschine darstellt, die immer terminiert. Dadurch würde die erste Maschine, die auf der Kodierung w1 agiert sozusagen wegfallen und es würde nur noch die Maschine übrig bleiben, die auf der Kodierung w2 agiert, was auch mit dem Halteproblem übereinstimmt, denn hier haben wir ebenfalls nur eine Kodierung und eine Eingabe.

Nette Grüße
Zu53