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).

Title	Post correspondence problem
Canonical name	PostCorrespondenceProblem
Date of creation	2013-03-22 19:09:59
Last modified on	2013-03-22 19:09:59
Owner	CWoo (3771)
Last modified by	CWoo (3771)
Numerical id	6
Author	CWoo (3771)
Entry type	Definition
Classification	msc 68Q45