[Overview] [Previous] [Next]

Post's Correspondence Problem

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

A = (w₁, w₂, w₃, ..., w_k) and B = (x₁, x₂, x₃, ..., x_k)

Post's Correspondence Problem is the following. Does there exist a sequence of integers i₁, i₂, i₃, ..., i_m such that m 1 and

w_i1w_i2w_i3...w_im = x_i1x_i2x_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.