Figure 9.7: Reductions turn positive instances into positive, and negative to negative

As suggested in Fig. 9.7, a reduction must turn any instance of Pi that has a yes answer into an instance of P2 with a yes answer, and every instance of Pi with a no answer must be turned into an instance of Pa with a no answer. Note that it is not essential that every instance of P2 be the target of one or more instances of Pi, and in fact it is quite common that only a small

9.3 Undecidable Problems About Turing Machines

We shall now use the languages L and L, whose status regarding decidability and recursive enumerability we know, to exhibit other undecidable or non-RE languages. The reduction technique wUl be exploited in each of these proofs. Our first undecidable problems are all about Turing machines. In fact, our discussion in this section culminates with the proof of Rices theorem, which says that any nontrivial property of Turing machuies that depends only on the language the TM accepts must be undecidable. Section 9.4 will let us investigate some undecidable problems that do not involve Turing machines or their languages.

9.3.1 Reductions

We introduced the notion of a reduction in Section 8.1.3. In general, if we have an algorithm to convert instances of a problem Pi to instances of a problem P-i that have the same answer, then we say that Pi reduces to P-z- We can use this proof to show that P-i is at least as hard as Pi. Thus, if Pi is not recursive, then Pj cannot be recursive. If Pi is non-RE, then Pa cannot be RE. As we mentioned in Section 8.1.3, you must be careful to reduce a known hard problem to one you wish to prove to be at least as hard, never the opposite.

fraction of P2 is a target of the reduction.

Formally, a reduction from Pi to P2 is a Turing machine that takes an instance of Pi written on its tape and halts with an instance of P2 on its tape. In practice, we shall generally describe reductions as if they were computer programs that take an instance of Pi as input and produce an instance of Pi as output. The equivalence of Turing machines and computer programs allows us to describe the reduction by either means. The importance of reductions is emphasized by the following theorem, of which we shall see numerous applications.

Theorem 9.7: If there is a reduction from Pi to P2, then:

a) If Pi is undecidable then so is P2.

b) If Pl is non-RE, then so is P2.

PROOF: First suppose Pj is undecidable. If it is possible to decide P2, then we can combine the reduction from Pj to P2 with the algorithm that decides P2 to construct an algorithm that decides Pi. The idea was suggested in Fig. 8.7. In more detail, suppose we are given an instance w of Pi. Apply to w the algorithm that converts w into an instance x of-P24 Then apply the algorithm that decides to P2 to x. If that algorithm says yes?\then x is in P2. Because we reduced Pi to P2, we know the answer to w for Pi is yes ; i.e., w is in Pi. Likewise, if x is not in P2 then w is not in Pi, and whatever answer we give to the question is x in P2? is also the correct answer to is w in Pi?

We have thus contradicted the assumption that Pi is undecidable. Our conclusion is that if Pi is undecidable, then F2 is also undecidable.

Now, consider part (b). Assume that Pi is non-RE, but P2 is RE. Now, we have an algorithm to reduce Pi to P2, but we have only a procedure to recognize Pr, that is, there is a TM that says yes if its input is in P2 but may not halt if its input is not in P2. As for part (a), starting with an instance w of Pl, convert it by the reduction algorithm to an instance ж of P2. Then apply the TM for Ps to X. If x is accepted, then accept w.

This procedure describes a TM (which may not halt) whose language is Pi. If ги is in Pl, then x is in P2, so this TM will accept w. If го is not in Pi, then x is not in Pa. Then, the TM may or may not halt, but will surely not accept w. Since we assumed no TM for Pi exists, we have shown by contradiction that no TM for P2 exists either; i.e., if Pi is non-RE, then P2 is non-RE. □

9.3.2 Turing Machines That Accept the Empty Language

As an example of reductions involving Turing machines, let us investigate two languages called Le and L e. Each consists of binary strings. If w is a binary string, then it represents some TM, Mj, in the enumeration of Section 9.1.2.

If L{Mi) = 0, that is. Mi does not accept any input, then w is in Lc-Thus, Lg is the language consisting of all those encoded TMs whose language

is empty. On the other hand, if L{Mi) is not the empty language, then w is in Lrxe. Thus, Lne is the language of all codes for Turing machines that accept at least one input string.

In what follows, it is convenient to regard strings as the Turing machines they represent. Thus, we may define the two languages just mentioned as:

L, = {M\ LiM) = 0} . = {M ! LiM) Ф 0}

Notice that L and L e are both languages over the binary alphabet {0,1}, and that they are complements of one another. We shall see that L e is the easier of the two languages; it is RE but not recursive. On the other hand, Le is non-RE.

Theorem 9.8: Lne is recursively enumerable.

PROOF: We have only to exhibit a TM that accepts Lm- It is easiest to describe a nondeterministic TM M, whose plan is shown in Fig. 9.8. By Theorem 8.11, M can be converted to a deterministic TM.

Accept

Figure 9.8: Construction of a NTM to accept L e

The operation of M is as foUows-

1. M takes as input a TM code Mj.

2. Using its nondeterministic capability, M guesses an mput w that Mi might accept.

3. M tests whether Mi accepts w. For this part, M can simidate the universal TM и that accepts Lu-

4. If Mi accepts w, then M accepts its own input, which is Mi.

In this manner, if Mi accepts even one string, M will guess that string (among all others, of course), and accept Mj. However, if £(Mj) = 0, then no guess w leads to acceptance by Mi, so M does not accept Mj. Thus, i(M) - Lne-