Figure 9.11: Reductions proving the undecidabiiity of Posts Correspondence Problem

9.4.1 Definition of Posts Correspondence Problem

An instance of Posts Correspondence Problem (PCP) consists of two lists of strings over some alphabet E; the two lists must be of equal length. We generally refer to the A and D lists, and write A = wi,w-2t .. ,Wk and В = ,жз,...,а:, for some integer k. For each i, the pair {wi.,Xi) is said to be a corresponding pair.

We say this instance of PCP has a solution, if there is a sequence of one or more integers Jl, ia, -.im that, when uiterpreted as indexes for strings in the A and В Usts, yield the same string. That is, гуШг - xiXi -Xj. We say the sequence ii,i-2,.. ,im is a solution to this instance of PCP, if so. The Posts correspondence problem b:

Given an instance of PCP, tell whether this instance has a solution.

Example 9.13: Let S = {0,1}, and let the A and В lists be as defined in Fig. 9.12. In this case, PCP has a solution. For instance, let m = 4, - 2, h = l,h- 1, and J4 = 3; i.e., the solution is the list 2,1,1,3. We verify that this list is a solution by concatenating the corresponding strings in order for the two lists. That is, W2WiW\Wz = X2XiXiXz - 101111110. Note this solution is not unique. For instance, 2,1.1,3,2,1,1.3 is another solution. □

9.4 Posts Correspondence Problem

In this section, we begin reducing undecidable questions about Turing machines to undecidable questions about real things, that is, common matters that have nothing to do with the abstraction of the Turing machine. We begin with a problem called Posts Correspondence Problem (PCP), which is stUl abstract, but it involves strings rather than Turing machines. Our goal is to prove this problem about strings to be undecidable, and then use its undecidabiiity to prove other problems undecidable by reducing POP to those.

We shall prove PCP undecidable by reducing to PCP. To facilitate the proof, we introduce a modified PCP, and reduce the modified problem to the original PCP. Then, we reduce L to the modified PCP. The chain of reductions is suggested by Fig. 9.11. Since the original is known to be undecidable, we conclude that PCP is undecidable.

Figure 9.12; An instance of PCP

PCP as a Language

Since we are discussing the problem of deciding whether a given instance of PCP has a solution, we need to express this problem as a language. As PCP allows instances to have arbitrary alphabets, the language PCP is really a set of strings over some fixed alphabet, which codes instances of PCP, much as we coded Turing machines that have arbitrary sets of states and tape symbols, in Section 9.1.2. For example, if a PCP instance has an alphabet with up to 2* symbols, we can use distujct fc-bit binary codes for each of the symbols.

Since each PCP instance has a finite alphabet, we can find some A; for each instance. We can then code all instances in a 3-symbol alphabet consisting of 0, 1, and a comma symbol to separate strings. We begin the code by writing к in binary, followed by a comma. Then follow each of the pairs of strings, with strings separated by commas and their symbols coded in a fc-bit binary code.

Example 9.14: Here is an example where there is no solution. Again we let S = {0,1}, but now the instance is the two fists given in Fig. 9.13.

Suppose that the PCP instance of Fig. 9.13 has a solution, say i], г2,... ,ir-n., for some m > 1. We claim ii = 1. For if и - 2, then a string beginning with W2 =011 would have to equal a string that begins with X2 - 11. But that equality is impossible, since the first symbols of these two strings are 0 and 1, respectively. SimUarly, it is not possible that ij - 3, since then a string beginning with U13 = 101 would have to equal a string beginning with хз = Oil.

If ii = 1, then the two corresponding strings from lists A and В would have to begin:

A: 10-- B: 101

Now, let us see what iz could be.

1. If 2 = 1, then we have a problem, since no string beginning with WiWi -

Figure 9.13: Another PCP instance

1010 can match a string that begins with xiXi = 101101; they must disagree at the fourth position.

2. If i2 ~ 2, we again have a problem, because no string that begins with wiW2 - 10011 can match a string that begins with Xix-2 = 10111; they must differ at the third position.

3. Only - 3 is possible.

If we choose = 3, then the corresponding strings formed from list of integers iiJs are:

A: lOlOl--B: 101011---

There is nothing about these strings that immediately suggests we cannot extend list 1,3 to a solution. However, we can argue that it is not possible to do so. The reason is that we are in the same condition we were in after choosing ii = 1. The string from the В list is the same as the string from the A list except that in the В list there is an extra 1 at the end. Thus, we are forced to choose = 3, г4 = 3, and so on, to avoid creating a mismatch. We can never allow the A string to catch up to the В string, and thus can never reach a solution. □

9.4.2 The Modified PCP

It is easier to reduce Lu to PCP if we first introduce an intermediate version of PCP, which we call the Modified Posts Correspondence Problem, or MPCP. In the modified PCP, there is the additional requirement on a solution that the first pair on the A and В lists must be the first pair in the solution. More formally, an instance of MPCP is two lists A = wi,W2,.. ,Шк and В = xi,X2, .-.Xk, and a solution is a list of 0 or more integers iiA2,---,im such that

WiWi,Wi = XiXiXi- ir

Notice that the pair [vn,Xi) is forced to be at the beginning of the two strings, even though the index 1 is not mentioned at the front of the list that