The Post correspondence problem is an undecidable decision problem that was introduced by Emil Post. Because it is simpler than the Halting problem and the Entscheidungsproblem it is often used in proofs of undecidability.
Informally the problem can be described as follows. Given a dictionary that contains pairs of phrases, i.e., a list of words, that mean the same, decide if there is a sentence that means the same in both languages.
Definition of the problem
The input of the problem consists of two finite lists:
of words over some alphabet Σ with at least two symbols. A solution to this problem is a sequence of indexes i_{1}, ..., i_{k}, 1 <= i_{j} <= n, such that
- u_{i1}...u_{ik} = v_{i1}...v_{ik}.
Example of an instance of the problem
Consider the following two lists:
u_{1} u_{2} u_{3} u_{4} v_{1} v_{2} v_{3} v_{4} "aba" "bbb" "aab" "bb" "a" "aaa" "abab" "babba"A solution to this problem would be the sequence 1, 4, 3, 1 because
- u_{1}u_{4}u_{3}u_{1} = "ababbaababa" = v_{1}v_{4}v_{3}v_{1}