The Post correspondence problem is an undecidable decision problem that was introduced by Emil Post in 1946. Because it is simpler than the halting problem and the Entscheidungsproblem it is often used in proofs of undecidability.

Let ${\displaystyle A}$ be an alphabet with at least two symbols. The input of the problem consists of two finite lists ${\displaystyle \alpha _{1},\ldots ,\alpha _{N}}$ and ${\displaystyle \beta _{1},\ldots ,\beta _{N}}$ of words over ${\displaystyle A}$. A solution to this problem is a sequence of indices ${\displaystyle (i_{k})_{1\leq k\leq K}}$ with ${\displaystyle K\geq 1}$ and ${\displaystyle 1\leq i_{k}\leq N}$ for all ${\displaystyle k}$, such that

The decision problem then is to decide whether such a solution exists or not.

This gives rise to an equivalent alternative definition often found in the literature, according to which any two homomorphisms ${\displaystyle g,h}$ with a common domain and a common codomain form an instance of the Post correspondence problem, which now asks whether there exists a nonempty word ${\displaystyle w}$ in the domain such that

Another definition describes this problem easily as a type of puzzle. We begin with a collection of dominos, each containing two strings, one on each side. An individual domino looks like

and a collection of dominos looks like

The task is to make a list of these dominos (repetition permitted) so that the string we get by reading off the symbols on the top is the same as the string of symbols on the bottom. This list is called a match. The Post correspondence problem is to determine whether a collection of dominos has a match. For example, the following list is a match for this puzzle.

For some collections of dominos, finding a match may not be possible. For example, the collection