## You are here

HomePost correspondence problem

## Primary tabs

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

## Mathematics Subject Classification

68Q45*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections