Post correspondence problem

 related topics {math, number, function} {style, bgcolor, rowspan} {system, computer, user} {area, part, region} {@card@, make, design}

The Post correspondence problem is an undecidable decision problem that was introduced by Emil Post in 1946.[1] Because it is simpler than the halting problem and the Entscheidungsproblem it is often used in proofs of undecidability.

Contents

Definition of the problem

The input of the problem consists of two finite lists $\alpha_{1}, \ldots, \alpha_{N}$ and $\beta_{1}, \ldots, \beta_{N}$ of words over some alphabet A having at least two symbols. A solution to this problem is a sequence of indices $(i_k)_{1 \le k \le K}$ with $K \ge 1$ and $1 \le i_k \le N$ for all k, such that

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

Example 1

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 α23 and β23, 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:

Example 2

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):