Let be a finite alphabet, and let A and B be two lists of nonempty strings over , with |A|=|B|. That is,

A = (w_{1}, w_{2}, w_{3}, ..., w_{k})
and B = (x_{1}, x_{2}, x_{3}, ..., x_{k})

*Post's Correspondence Problem* is the following. Does there exist a sequence
of integers i_{1}, i_{2}, i_{3}, ..., i_{m}
such that m 1 and

w_{i1}w_{i2}w_{i3}...w_{im}
= x_{i1}x_{i2}x_{i3}...x_{im}
?

**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