# Post correspondence problem

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

 $(u_{1},v_{1}),\ldots,(u_{n},v_{n})$

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

 $u_{1}\cdots u_{n}=v_{1}\cdots v_{n}.$

The word $u_{1}\cdots u_{n}$ is called a match in $P$.

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

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

is a correspondence in $P$.

On the other hand, there are no correspondences in $\{(ab,a),(a,ba^{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).

Title Post correspondence problem PostCorrespondenceProblem 2013-03-22 19:09:59 2013-03-22 19:09:59 CWoo (3771) CWoo (3771) 6 CWoo (3771) Definition msc 68Q45