If we take
there cannot be any PC-solution simply because any string composed of
elements of A will be longer than the corresponding string from B.
In specific instances we may be able to show by explicit construction that a
pair ( A,B) permits a PC-solution, or we may be able to argue, as we did
previously, that no such solution can exist. But in general, there is no algorithm
for deciding this question under all circumstances. The Post correspondence
problem is therefore undecidable.
To show this is a somewhat lengthy process. For the sake of clarity, we break
it into two parts. In the first part, we introduce the modified Post
correspondence problem. We say that the pair (A,B) has a modified Post
correspondence solution (MPC solution) if there exists a sequence of integers
i,j…,k, such that
w 1 w i w j …w k = v l v i v j …v k .
In the modified Post correspondence problem, the first elements of the sequences
A and B play a special role. An MPC solution must start with w 1 on the left side
and with v 1 on the right side. Note that if there exists an MPC solution, then
there is also a PC solution, but the converse is not true.
The modified Post correspondence problem is to devise an algorithm for
deciding if an arbitrary pair (A,B) admits an MPC solution. This problem is also
undecidable. We will demonstrate the undecidability of the modified Post
correspondence problem by reducing a known undecidable problem, the
membership problem for recursively enumerable languages, to it. To this end, we
introduce the following construction. Suppose we are given an unrestricted
grammar G = (V,T,S,P) and a target string w. With these, we create the pair (A,
B) as shown in Figure 12.8. In Figure 12.8, the string FS ⇒ is to be taken as w 1
and the string F as v 1 . The order of the rest of the strings is immaterial.
Figure 12.8
there cannot be any PC-solution simply because any string composed of
elements of A will be longer than the corresponding string from B.
In specific instances we may be able to show by explicit construction that a
pair ( A,B) permits a PC-solution, or we may be able to argue, as we did
previously, that no such solution can exist. But in general, there is no algorithm
for deciding this question under all circumstances. The Post correspondence
problem is therefore undecidable.
To show this is a somewhat lengthy process. For the sake of clarity, we break
it into two parts. In the first part, we introduce the modified Post
correspondence problem. We say that the pair (A,B) has a modified Post
correspondence solution (MPC solution) if there exists a sequence of integers
i,j…,k, such that
w 1 w i w j …w k = v l v i v j …v k .
In the modified Post correspondence problem, the first elements of the sequences
A and B play a special role. An MPC solution must start with w 1 on the left side
and with v 1 on the right side. Note that if there exists an MPC solution, then
there is also a PC solution, but the converse is not true.
The modified Post correspondence problem is to devise an algorithm for
deciding if an arbitrary pair (A,B) admits an MPC solution. This problem is also
undecidable. We will demonstrate the undecidability of the modified Post
correspondence problem by reducing a known undecidable problem, the
membership problem for recursively enumerable languages, to it. To this end, we
introduce the following construction. Suppose we are given an unrestricted
grammar G = (V,T,S,P) and a target string w. With these, we create the pair (A,
B) as shown in Figure 12.8. In Figure 12.8, the string FS ⇒ is to be taken as w 1
and the string F as v 1 . The order of the rest of the strings is immaterial.
Figure 12.8