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.
Definition of the problem
The input of the problem consists of two finite lists and of words over some alphabet A having at least two symbols. A solution to this problem is a sequence of indices with and for all k, such that
The decision problem then is to decide whether such a solution exists or not.
Example instances of the problem
Consider the following two lists:
A solution to this problem would be the sequence (3, 2, 3, 1), because
Furthermore, since (3, 2, 3, 1) is a solution, so are all of its "repetitions", such as (3, 2, 3, 1, 3, 2, 3, 1), etc.; that is, when a solution exists, there are infinitely many solutions of this repetitive kind.
However, if the two lists had consisted of only α2,α3 and β2,β3, then there would have been no solution (because then no matching pair would have the same last letter, as must occur at the end of a solution).
A convenient way to view an instance of a Post correspondence problem is as a collection of blocks of the form
there being an unlimited supply of each type of block. Thus the above example is viewed as
where the solver has an endless supply of each of these three block types. A solution corresponds to some way of laying blocks next to each other so that the string in the top cells corresponds to the string in the bottom cells. Then the solution to the above example corresponds to:
Again using blocks to represent an instance of the problem, the following is an example that has infinitely many solutions in addition to the kind obtained by merely "repeating" a solution. For readability, just the block number is shown below each block:
In this instance, every sequence of the form (1, 2, 2, ..., 2, 3) is a solution (in addition to all their repetitions):
Full article ▸