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
( g_{i} , h_{i} ) in the alphabet A
there is a sequence i_{1} i_{2} ... i_{N}
of selections such that the strings
g_{i1}g_{i2} ... g_{iN}
and
h_{i1}h_{i2} ... h_{iN}
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}
g_{1} = abc
 g_{2} = abba
 g_{3} = c
 g_{4} = bbba
 g_{5} = abcc

h_{1} = ab
 h_{2} = aabb
 h_{3} = ccc
 h_{4} = cbbb
 h_{5} = aab

In attempting to solve the problem we might choose i_{1} to
be 1 and i_{2} 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 i_{3} 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.
RaywardSmith