Das Fotonexus-Wiki befindet sich im Testbetrieb.
Postsches Korrespondenzproblem
Aus Fotonexus.
Das Postsche Korrespondenzproblem (nach Emil Leon Post) ist ein Beispiel für ein unentscheidbares Problem in der Theoretischen Informatik. Es wird häufig verwendet, um mittels Reduktion die Unentscheidbarkeit anderer Probleme zu zeigen.
Gegeben ist eine endliche Folge Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): P
von Paaren Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): \left((x_1,y_1),(x_2,y_2),\ldots,(x_m,y_m)\right) von nicht-leeren Wörtern Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): x_1, x_2, \ldots, x_m, y_1, y_2, \ldots, y_m über einem endlichen Alphabet.
Als Entscheidungsproblem stellt sich nun die folgende Frage: Existiert eine nicht-leere Folge Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): I = i_1, i_2, \ldots, i_n
von Indizies aus Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): \{1, 2, \ldots, m\}
, so dass die Verkettung (Konkatenation) der Wörter Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): \left. {x_{i_1},x_{i_2},\ldots,x_{i_n}}\right.
gleich der Verkettung der Wörter Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): \left.{y_{i_1},y_{i_2},\ldots,y_{i_n}}\right.
ist?
Inhaltsverzeichnis |
Anschauliche Interpretation
Wie oben erklärt, besitzt jede der beiden gegebenen Listen Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): m -viele Worte über dem Eingabealphabet. Die paarweise Darstellung der Elemente, sprich Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): \left((x_1,y_1),(x_2,y_2),\ldots,(x_m,y_m)\right) , kann man sich dabei sehr gut als "Dominosteine" (oder auch andere, beschreibbare Spielsteine) darstellen: Es gibt Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): m -viele Dominosteine und von jedem Typ stehen unendlich viele Dominosteine des gleichen Typs zur Verfügung. Dabei steht auf einem Dominostein Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): d_i
auf der oberen Hälfte das Wort Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): x_i
und auf der unteren Hälfte das Wort Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): y_i \ \forall i \in \left\{ 1 , ... , m \right\}
geschrieben.
Das PKP lässt sich nun also wie folgt verstehen: Welche Dominosteine müssen in welcher Reihenfolge hintereinander gelegt werden, so dass die Worte auf der oberen Hälfte der Dominosteine (von links nach rechts gelesen) dasselbe Wort ergeben, wie die (von links nach rechts gelesenen) Worte aus der unteren Hälfte der zusammengelegten Dominosteine?
Beispiel
Gegeben:
Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): P_1 = \left( (1,101), (10,00), (011,11) \right)
Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): \left. x_1=1 \right.,
Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): \left. y_1=101 \right.
Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): \left. x_2=10 \right.,
Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): \left. y_2=00 \right.
Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): \left. x_3=011 \right.,
Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): \left. y_3=11 \right.
Lösung:
Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): I_1 = \left( 1, 3, 2, 3 \right)
Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): \left. {1|0\ 1\ 1|1\ 0|0\ 1\ 1} \right.
Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): \left. {1\ 0\ 1|1\ 1|0\ 0|1\ 1} \right.
Resultat:
Die beiden verketteten Wörter sind identisch, d.h. die PCP-Instanz Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): P_1
ist beispielsweise mit der Indexfolge Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): \left(1, 3, 2, 3\right)
lösbar.
Manchmal gibt es mehrere primitive Lösungen, was in diesem Beispiel jedoch nicht der Fall ist. Natürlich bildet jede vollständige Verkettung einer solchen Indexfolge mit sich selbst oder einer anderen Lösung wieder eine Lösung.
Das Beispiel Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): P_1
erweckt vielleicht den Eindruck, dass das Postsche Korrespondenzproblem gar nicht so schwierig ist. Jedoch muss ein adäquater Lösungsalgorithmus für alle Instanzen eine korrekte Antwort geben, d.h. er muss in endlicher Zeit entscheiden, ob eine solche Indexfolge Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): I für ein gegebenes Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): P existiert oder nicht.
Grenzen der Unentscheidbarkeit
Das obige Entscheidungsproblem ist zwar im Allgemeinen unentscheidbar, lässt man jedoch nur Wortpaare über einem unären Alphabet (Alphabet mit nur einem Symbol) zu oder schränkt man die Anzahl der Paare in Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): P
zu stark ein, dann wird das Problem doch wieder entscheidbar. Andererseits reicht ein binäres Alphabet (Alphabet mit zwei Symbolen) für die Unentscheidbarkeit aus, weil größere Alphabete damit einfach kodiert werden können.
Siehe auch
Weblinks
- PCP-Lösungsprogramm für Windows (für Windows 95/98/NT/2000/XP/2003)
- PCP@HOME Liste von schweren PCP-Instanzen und ein PCP-Puzzle (Java Applet)
| Dieses Dokument entstammt in seiner ersten oder einer späteren Version der deutschsprachigen Wikipedia. Es ist dort zu finden unter dem Stichwort Postsches_Korrespondenzproblem, die Liste der bisherigen Autoren befindet sich in der Versionsliste; die Originalfassung kann dort auch bearbeitet werden. Alle Texte der Wikipedia und ihre Derivate stehen unter der GNU-Lizenz für freie Dokumentation. |
