where w ij and v ij denote the jth letter of w i and v i , respectively, and m i = |w i |, r i =
|v i |. In words, y i is created from w i by appending to each character, while z i is
obtained by prefixing each character of v i with To complete the definition of C
and D, we take
Consider now the pair (C,D), and suppose it has a PC solution. Because of the
placement of and , such a solution must have y 0 on the left and y n+1 on the
right and so must look like
Figure 12.13
MPC algorithm.
y n+1 on the right and so must look like
Ignoring the characters and we see that this implies
w 1 w j …w k = v 1 v j …v k ,
so that the pair (A, B) permits an MPC solution.
We can turn the argument around to show that if there is an MPC solution for
(A,B) then there is a PC solution for the pair (C,D).
Assume now that the Post correspondence problem is decidable. We can then
construct the machine shown in Figure 12.13. This machine clearly decides the
modified Post correspondence problem. But the modified Post correspondence