Registrierung Kalender Mitgliederliste Teammitglieder Suche Häufig gestellte Fragen Zur Startseite

Informatiker Board » Themengebiete » Theoretische Informatik » Berechenbarkeits- und Komplexitätstheorie » Reduktion des allgemeinen Halteproblems auf ein Problem P1 » Hallo Gast [Anmelden|Registrieren]
Letzter Beitrag | Erster ungelesener Beitrag Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen
Neues Thema erstellen Antwort erstellen
Zum Ende der Seite springen Reduktion des allgemeinen Halteproblems auf ein Problem P1
Beiträge zu diesem Thema Autor Datum
 Reduktion des allgemeinen Halteproblems auf ein Problem P1 Zu53 03.02.2019 03:49
 RE: Reduktion des allgemeinen Halteproblems auf ein Problem P1 ed209 03.02.2019 22:08
 RE: Reduktion des allgemeinen Halteproblems auf ein Problem P1 Zu53 04.02.2019 09:42

Autor
Beitrag « Vorheriges Thema | Nächstes Thema »
Zu53
Grünschnabel


Dabei seit: 03.02.2019
Beiträge: 2

Reduktion des allgemeinen Halteproblems auf ein Problem P1 Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

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
03.02.2019 03:49 Zu53 ist offline Beiträge von Zu53 suchen Nehmen Sie Zu53 in Ihre Freundesliste auf
ed209
Routinier


Dabei seit: 07.09.2006
Beiträge: 317

Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

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
03.02.2019 22:08 ed209 ist offline E-Mail an ed209 senden Beiträge von ed209 suchen Nehmen Sie ed209 in Ihre Freundesliste auf
Zu53
Grünschnabel


Dabei seit: 03.02.2019
Beiträge: 2

Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

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
04.02.2019 09:42 Zu53 ist offline Beiträge von Zu53 suchen Nehmen Sie Zu53 in Ihre Freundesliste auf
Baumstruktur | Brettstruktur
Gehe zu:
Neues Thema erstellen Antwort erstellen
Informatiker Board » Themengebiete » Theoretische Informatik » Berechenbarkeits- und Komplexitätstheorie » Reduktion des allgemeinen Halteproblems auf ein Problem P1