Post correspondence problem

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.

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 some alphabet ${\displaystyle A}$ having at least two symbols. 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

...
Wikipedia