Informatik

Was ist das Postsche Korrespondenzproblem?

Gegeben sind Paare von Wörtern $(u_i,v_i)$. Gesucht ist eine nichtleere Indexfolge $i_1,\dots,i_k$ mit

$$u_{i_1}\cdots u_{i_k}=v_{i_1}\cdots v_{i_k}.$$

Das Problem ist unentscheidbar.

Bild