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