[Overview] [Previous] [Next]

Post's Correspondence Problem

Let sigma be a finite alphabet, and let A and B be two lists of nonempty strings over sigma, 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