VL-07 Das Postsche Korrespondanzproblem Flashcards
Was ist das Postsche Korrepondanzproblem (PCP)?
Das PCP besteht aus Dominosteinen, welche aus einem Wort x auf der Oberseite und einem Wort y auf der Unterseite bestehen. Das Ziel ist es eine Indize Reihenfolge zu finden so dass beide Seiten das gleiche Wort bilden.
Was ist das Modifizierte Postsche Korrenspondanzproblem (MPCP)?
Das MPCP legt einen Dominostein als Startstein i0 fest.
Wie lässt sich beweisen, dass das PKP unentscheidbar ist?
Der Beweis erfolgt per Reduktion H < MPCP < PCP:
Zunächst wird das MPCP auf PCP reduziert. Dazu werden die Dominosteine so modifiziert, dass eine Lösung des PCP nur mit dem Startdomino i0 möglich ist.
Anschließend wird H auf MPCP reduziert, indem die Konfiguration einer TM als Domionsteine kodiert wird. Durch das Lösen des MPCP wird somit das Halteproblem gelöst, was unentscheidbar ist.
