Post correspondence problem

The Post correspondence problem is an undecidable decision problem that was introduced by Emile 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:

u₁, ..., u_n and v₁, ..., v_n

of words over some alphabet Σ with at least two symbols. A solution to this problem is a sequence of indexes i₁, ..., i_k, 1 <= i_j <= n, such that

u_i₁...u_{i_k} = v_i₁...v_{i_k}.

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

Example of an instance of the problem

Consider the following two lists:

        u₁    u₂    u₃    u₄     v₁    v₂     v₃     v₄
      "aba" "bbb" "aab" "bb"    "a" "aaa" "abab" "babba"

A solution to this problem would be the sequence 1, 4, 3, 1 because

u₁u₄u₃u₁ = "ababbaababa" = v₁v₄v₃v₁

If the two lists would have consisted of, for example, only u₁, u₂, u₃ and v₁, v₂, v₃ then there would have been no solution.