Encyclopedia > Post correspondence problem

  Article Content

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:

u1, ..., un and v1, ..., vn

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

ui1...uik = vi1...vik.

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:

        u1    u2    u3    u4     v1    v2     v3     v4
      "aba" "bbb" "aab" "bb"    "a" "aaa" "abab" "babba"
A solution to this problem would be the sequence 1, 4, 3, 1 because

u1u4u3u1 = "ababbaababa" = v1v4v3v1

If the two lists would have consisted of, for example, only u1, u2, u3 and v1, v2, v3 then there would have been no solution.

All Wikipedia text is available under the terms of the GNU Free Documentation License

  Search Encyclopedia

Search over one million articles, find something about almost anything!
  Featured Article

... negative, though opinions differ. Making a complete assessment is impossible on publically available information. Whilst the Typhoon lacks the all-aspect steal ...

This page was created in 34.7 ms