PCP

Gegeben ist eine endliche Folge von Wortpaaren (Dominosteinen) über einem Alphabet $Σ$ :

K = ⟨ (x_{1}, y_{1}), (x_{2}, y_{2}), \dots, (x_{k}, y_{k}) ⟩

Das Postsche Korrespondenzproblem fragt, ob es eine nicht-leere Indexfolge $i_{1}, i_{2}, \dots, i_{m} \in {1, \dots, k}$ gibt, sodass gilt:

x_{i_{1}} x_{i_{2}} \dots x_{i_{m}} = y_{i_{1}} y_{i_{2}} \dots y_{i_{m}}

Dieses Problem ist unentscheidbar.