Post's Correspondence Problem

In 1947 Post showed that there is no effective procedure to answer questions of the following kind:

The correspondence problem

Given an alphabet A and a finite set of pairs of words ( gi , hi ) in the alphabet A there is a sequence i1 i2 ... iN of selections such that the strings
gi1gi2 ... giN and hi1hi2 ... hiN
formed by concatenating - writing down in order - corresponding g's and h's are identical?

From "Computation, Finite and Infinite Machines" by Marvin Minsky

An example

A={a, b, c}
g1 = abc g2 = abba g3 = c g4 = bbba g5 = abcc
h1 = ab h2 = aabb h3 = ccc h4 = cbbb h5 = aab
In attempting to solve the problem we might choose i1 to be 1 and i2 to be 3. The g sequence thus far would then be abcc while the h sequence would be abccc. Clearly the sequences are not identical.
Extending this sequence by chosing i3 to be 3 gives the sequences abccc and abcccccc, the sequences are still not equal nor does this extension seem fruitful.
Try the problem using the PCP machine.

The extraordinary feature of these problems is that they cannot be solved in general (of course the above instance of the problem may be solved - the answer is yes). No program can be written which can accept such problems as input and respond "yes" or "no" accurately every time. Proof of this can be found in Minsky's "Computation, Finite and Infinite Machines" and also in the rather more accessible "A first course in Computability" by V. J. Rayward-Smith