MPC solution if and only if w ∈ L (G).
Suppose now we assume that the modified Post correspondence problem is
decidable. We can then construct an algorithm for the membership problem of G
as sketched in Figure 12.12. An algorithm for constructing A from B from G and
w clearly exists, but a membership algorithm for
Figure 12.12
Membership algorithm.
G and w does not. We must therefore conclude that there cannot be any
algorithm for deciding the modified Post correspondence problem.
With this preliminary work, we are now ready to prove the Post
correspondence problem in its original form.
Theorem 12.7
The Post correspondence problem is undecidable.
Proof: We argue that if the Post correspondence problem were decidable, the
modified Post correspondence problem would be decidable.
Suppose we are given sequences A = w 1 ,w 2 …,w n and B = v 1 ,v 2 …,v n on some
alphabet Σ. We then introduce new symbols and and the new sequences
defined as follows. For i =1, 2,…n