interest, particularly in the area of context-free languages. But in many instances
it is cumbersome to work with the halting problem directly, and it is convenient
to establish some intermediate results that bridge the gap between the halting
problem and other problems. These intermediate results follow from the
undecidability of the halting problem, but are more closely related to the
problems we want to study and therefore make the arguments easier. One such
intermediate result is the Post correspondence problem.
The Post correspondence problem can be stated as follows. Given two
sequences of n strings on some alphabet Σ, say
A = w 1 ,w 2 ,…w n
and
B = v 1 ,v 2 ,…,v n ,
we say that there exists a Post correspondence solution (PC-solution) for pair
(A,B) if there is a nonempty sequence of integers i,j,…,k, such that
w i w j …w k = v i vj…v k .
The Post correspondence problem is to devise an algorithm that will tell us, for
any (A, B), whether or not there exists a PC-solution.
Example 12.5
Let Σ = {0,1} and take A and B as
For this case, there exists a PC-solution as Figure 12.7 shows.
Figure 12.7