Let be a finite alphabet,
and let A and B be two lists of nonempty strings over
,
with |A|=|B|. That is,
A = (w1, w2, w3, ..., wk) and B = (x1, x2, x3, ..., xk)
Post's Correspondence Problem is the following. Does there exist a sequence
of integers i1, i2, i3, ..., im
such that m 1 and
wi1wi2wi3...wim = xi1xi2xi3...xim ?
Example. Suppose A = (a, abaaa, ab) and B = (aaa, ab, b). Then the required sequence of integers is 2,1,1,3, giving
abaaa a a ab = ab aaa aaa b.
This example had a solution. It will turn out that Post's correspondence problem is insoluable in general.
Copyright © 1996 by David Matuszek
Last modified Mar 27, 1996