Post correspondence problem

Let $\mathrm{\Sigma }$ be an alphabet. As usual, ${\mathrm{\Sigma }}^{+}$ denotes the set of all non-empty words over $\mathrm{\Sigma }$. Let $P\subset {\mathrm{\Sigma }}^{+}\times {\mathrm{\Sigma }}^{+}$ be finite. Call a finite sequence

$$(u_1,v_1),\mathrm{\dots },(u_n,v_n)$$

of pairs in $P$ a correspondence in $P$ if

$$u_1\mathrm{\cdots }{u}_n=v_1\mathrm{\cdots }{v}_n.$$

The word $u_1\mathrm{\cdots }{u}_n$ is called a match in $P$.

For example, if $\mathrm{\Sigma }=\{a,b\}$, and $P=\{(b,b^2),(a^2,a),(b^{2}a,b^3),(a{b}^2,a^{2}b)\}$. Then

$$(a^2,a),(a{b}^2,a^{2}b),(b^{2}a,b^3),(a{b}^2,a^{2}b),(b,b^2)$$

is a correspondence in $P$.

On the other hand, there are no correspondences in $\{(ab,a),(a,b{a}^2)\}$.

The Post correspondence problem asks the following:

Is there an algorithm (Turing machine or any other equivalent computing models) such that when an arbitrary $P$ is given as an input, returns $1$ if there exists a correspondence in $P$ and $0$ otherwise.

The problem is named after E. Post because he proved

Theorem 1.

The Post correspondence problem is unsolvable (no such algorithms exist).