CHAPTER 9. UNDECWABILITY

Our next step is to prove that L e is not recursive. To do so, we reduce to L e. That is, we shall describe an algorithm that transforms an input {M,w) into an output M, the code for another Turing machine, such that w is in L{M) if and only if L(M) is not empty. That is, M accepts w if and only if M accepts at least one string. The trick is to have M ignore its input, and instead simulate M on input w. If M accepts, then M accepts its own input; thus acceptance of ш by M is tantamount to L(M) being nonempty. If L e were recursive, then we would have an algorithm to tell whether or not M accepts w: construct M and see whether L{M) = 0.

Theorem 9.9: L e is not recursive.

PROOF: We shall follow the outline of the proof given above. We must design an algorithm that converts an input that is a binaiy-coded pair (M, w) into a TM M such that L{M) ф 0 if and only if M accepts input w. The construction of M is sketched in Fig. 9.9. As we shall see, if M does not accept tu, then Af accepts none of its inputs; i.e., L{M) = 0. However, if M accepts w, then M accepts every input, and thus L{M) surely is not 0.

* Accept

Figure 9.9: Plan of the TM M constructed from (М.ги) m Theorem 9.9; M accepts arbitrary input if and only if M accepts w

M is designed to do the following:

L M ignores its own input x. Rather, it replaces its input by the string that represents TM M and input string w. Since M is designed for a specific pair {M,w), which has some length n, we may construct M to have a sequence of states qo,qi, ,gni where qo is the start state.

(a) In state gi, for i = 0,1,..., n - 1, M writes the (t + l)st bit of the code for (М,ш), goes to state gj-i, and moves right.

(b) In state g , M moves right, if necessary, replacing any nonblanks {which would be the tail of x, if that input to M is longer than n) by blanks.

2. When M reaches a blank in state g , it uses a similar collection of states to reposition its head at the left end of the tape.

3. Now, using additional states, M simulates a universal TM U on its present tape.

9.3.3 Rices Theorem and Properties of the RE Languages

The fact that languages like Le and L e are undecidable is actually a special case of a far more general theorem: all nontrivial properties of the RE languages are undecidable, in the sense that it is impossible to recognize by a Turing machine those binary strings that are codes for a TM whose language has the property. An example of a property of the RE languages is the language is context free. It is undecidable whether a given TM accepts a context-free language, as a special case of the general principle that all nontrivial properties of the RE languages are undecidable.

A property of the RE languages is simply a set of RE languages. Thus, the property of being context-free is formally the set of all CFLs. The property of being empty is the set {0} consisting of only the empty language.

4. If и accepts, then M accepts. If U never accepts, then M never accepts either.

The description of M above should be sufficient to convince you that you could design a Turing machine that would transform the code for M and the string w into the code for M. That is, there is an algorithm to perform the reduction of Lu to Lfte- We also see that if M accepts w, then M accepts whatever input X was origiueilly on its tape. The fact that x was ignored is irrelevant; the definition of acceptance by a TM says that whatever was placed on the tape, before commencing operation, is what the TM accepts. Thus, if M accepts w, then the code for M is in Ljg.

Conversely, if M does not accept w, then M never accepts, no matter what its input is. Hence, in this case the code for M is not in Lne- We have successfully reduced Lj, to Lne by the algorithm that constructs M from M and w; we may conclude that, since Lu is not recursive, neither is Lne- The existence of this reduction is sufficient to complete the proof. However, to illustrate the impact of the reduction, we shall take this argument one step further. If Lne were recursive, then we could develop an algorithm for Lu as follows:

1. Convert (M,w) to the TM M as above.

2. Use the hypothetical algorithm for Le to tell whether or not L(M) =0. If so, say M does not accept w; if L{M) ф 0, say M does accept w.

Since we know by Theorem 9.6 that no such algorithm for L exists, we have contradicted the assumption that Lne is recursive, and conclude that L. e is not recursive. □

Now, we know the status of Lg. If Le were RE, then by Theorem 9.4, both it and Lne would be recursive. Since Lne is not recursive by Theorem 9.9, we conclude that:

Theorem 9.10: Lg is not RE. □

Why Problems and Their Complennients are Different

Our intuition tells us that a problem and its complement are really the same problem. To solve one, we can use an algorithm for the other, and at the last step, complement the output: say yes instead of no, and vice-versa. That instinct is exactly right, as long as the problem and its complement are recursive.

However, as we discussed in Section 9.2.2, there are two other possibilities. First, neither the problem nor its complement are even RE. Then, neither can be solved by any kind of TM at all, so in a sense the two are again similar. However, the interesting case, typified by and L,ie, is when one is RE and the other is non-RE.

For the language that is RE, we can design a TM that takes an input w and searches for a reason why w is in the language. Thus, for Ье, given a TM M as input, we set our TM looking for strings that the TM M accepts, and as soon as we find one, we accept M, If M is a TM with an empty language, we never know for certain that M is not in Lne, but wc never accept M, and that is the correct response by the TM,

On the other hand, for the complement problem Le, which is not RE, there is no way ever to accept all its strings. Suppose we are given a string M that is a TM whose language is empty. We can test inputs to the TM M, and we may never find one that M accepts, yet we can never be sure that there isnt some input weve not yet tested, that this TM accepts. Thus, M can never be accepted, even if it should be.

A property is trivial if it is either empty (i.e., satisfied by no language at all), or is all RE languages. Otherwise, it is nontrivial.

Note that the empty property, 0, is different from the property of being an empty language, {$}.

We cannot recognize a set of languages as the languages themselves. The reason is that the typical language, being infinite, cannot be written down as a finite-length string that could be input to a TM. Rather, we must recognize the Turing machines that accept those languages; the TM code itself is finite, even if the language it accepts is infinite. Thus, if P is a property of the RE languages, the language L-p is the set of codes for Turing machines Mj such that L{Mi) is a language in V. When we talk about the decidability of a property P, we mean the decidability of the language L-p.

Theorem 9.11: (Rices Theorem) Every nontrivial property of the RE languages is undecidable.

PROOF: Let P be a nontrivial property of the RE languages. Assume to begin that 0, the empty language, is not in P; we shall return later to the opposite