Suchprobleme (3)

Beispiel 3 (PCP, Postsches Korrespondenz-Problem, Emil Post):

Gegeben ist eine Liste von Wort-Paaren. Gesucht ist eine Folge (von Kopien dieser Paare), bei der die Verkettung alle linken Seiten das gleiche Wort ergibt wie die Verkettung aller rechten Seiten.

Beispiele:

bba a b

b b ab

    $\begin{array}{c\vert c\vert c} aab & a & b \\ \hline a & b & aab \end{array}$

Das linke hat kürzeste Lösung [1, 1, 3, 2, 3, 3, 2, 3].

Aufgabe: finde Lösung für das rechte (es gibt eine).

Jetzt ist der Suchraum (alle Folgen) gar nicht beschränkt (die Folgen können beliebig lang sein).

Tatsächlich ist PCP nicht entscheidbar!

(Es gibt keinen Algorithmus, der für jede Liste von Paaren in endlicher Zeit korrekt entscheidet, ob es eine Lösungsfolge gibt.)