case. Since P is nontrivial, there must be some nonempty language L that is in P. Let Ml be a TM accepting L.

We shall reduce L to L-p, thus proving that Lp is undecidable, since Lj( is undecidable. The algorithm to perform the reduction takes as input a pair {M,w) and produces a TM M. The design of M is suggested by Fig. 9.10; L{M) is 0 if M does not accept and L(M) = L if M accepts w.

Accept

Figure 9.10: Construction of M for the proof of Rices Theorem

M is a two-tape TM. One tape is used to simulate M on w. Remember that the algorithm performing the reduction is given M and w as input, and can use this input in designing the transitions of M. Thus, the simulation of M on Ш is built into M; the latter TM does not have to read the transitions of M on a tape of its own.

The other tape of M is used to simulate Ml on the input x to M, if necessary. Again, the transitions of Ml are known to the reduction algorithm and may be built into the transitions of M. The TM M is constructed to do the following:

1. Simulate M on input w. Note that w is not the input to M; rather, M writes M and w onto one of its tapes and simulates the universal TM U on that pair, as in the proof of Theorem 9.8.

2. If M does not accept up, then M does nothing else. M never accepts its own input, X, so L{M) =0. Since we assume 0 is not in property V, that means the code for M is not in L-p.

3. If M accepts w, then M begins simulating Ml on its own input x. Thus, M will accept exactly the language L. Since L is in the code for M is in L-p.

You should observe that constructing M from M and w can he carried out by an algorithm. Since this algorithm turns (M, w] into an M that is in Lp if and only if (M,tt)) is in Lu, this algoritlun is a reduction of Lu to Lp, and proves that the property V is undecidable.

We are not quite done. We need to consider the case where 0 is in V. If so, consider the complement property V, the set of RE languages that do not have property P. By the foregoing, P is undecidable. However, since every TM

390 CHAPTER 9. UNDECWABmiTY

accepts an RE language, Lp, the set of (codes for) Turing machines that do not accept a language in P is the same as Lp, the set of TMs that accept a language in V. Suppose L-p were decidable. Then so would be Lp, because the complement of a recursive language is recursive (Theorem 9.3). □

9.3.4 Problems about Turing-Machine Specifications

All problems about Turing machines that involve only the language that the TM accepts are undecidable, by Theorem 9.11. Some of these problems are interesting in their own right. For instance, the following are undecidable:

1. Whether the language accepted by a TM is empty (which we knew from Theorems 9.9 and 9.3).

2. Whether the Ijmguage accepted by a TM is finite.

3. Whether the language accepted by a TM is a regular language.

4. Whether the language accepted by a TM is a context-free language.

However, Rices Theorem does not imply that everything about a TM is undecidable. For instance, questions that ask about the states of the TM, rather than about the language it accepts, could be decidable.

Example 9.12: It is decidable whether a TM has five states. The algorithm to decide this question simply looks at the code for the TM and counts the number of states that appear in any of its transitions.

As another example, it is decidable whether there exists some input such that the TM makes at least five moves. The algorithm becomes obvious when we remember that if a TM makes five moves, then it does so looking only at the nine cells of its tape stu-rounding its initial head position. Thus, we may simulate the TM for five moves on any of the finite number of tapes consisting of five or fewer input symbols, preceded and followed by blanks. If any of these simulations fails to reach a halting situation, then we conclude that the TM makes at least five moves on some input. □

9.3.5 Exercises for Section 9.3

* Exercise 9.3.1: Show that the set of Turing-machine codes for TMs that accept all inputs that are palindromes (possibly along with some other inputs) is undecidable.

Exercise 9.3,2: The Big Computer Corp. has decided to bolster its sagging market share by manufacturing a high-tech version of the T\iring machine, called BWTM, that is equipped with bells and whistles. The BWTM is basically the setme as your ordinary Turing machine, except that each state of the machine is labeled either a bell-state or a whistle-state. Whenever the BWTM enters

a new state, it either rings the bell or blows the whistle, depending on which type of state it has just entered. Prove that it is undecidable whether a given BWTM M, on given input w, ever blows the whistle.

Exercise 9.3.3: Show that the language of codes for TMs M that, when started with blank tape, eventually write a 1 somewhere on the tape is undecidable,

! Exercise 9.3.4; We know by Rices theorem that none of the following problems are decidable. However, are they recursively enumerable, or non-RE?

a) Does L(M) contain at least two strings?

b) Is L{M) infinite?

c) Is L(M) a context-free language?

* d) Is L(M) = (L(M))?

! Exercise 9.3.5: Let L be the language consisting of pairs of TM codes plus an integer, (M],M2,fc), such that L{Mi) П L{M2) contains at least к strings. Show that L is RE, but not recursive.

Exercise 9.3.6: Show that the following questions are decidable;

* a) The set of codes for TMs M such that, when started with blank tape

will eventually write some nonblank symbol on its tape. Hint: If M has m states, consider the first m transitions that it makes.

! b) The set of codes for TMs that never make a move left.

! c) The set of pairs (M,w) such that TM M, started with input vj, never scans any tape cell more than once.

! Exercise 9.3.7: Show that the following problems are not recursively enumerable:

* a) The set of pairs {M,w) such that TM M, started with input w, does not

halt.

b) The set of pahs (Mi, Ma) such that L(Mi) П 1(2) 0,

c) The set of triples (М1,М2,Мз) such that L{Mi) (Мз)(Мз); i.e., the language of the first is the concatenation of the languages of the other two TMs.

!! Exercise 9.3.8: Tell whether each of the following are recursive, RE-but-not-recursive, or non-RE.

* a) The set of all TM codes for TMs that halt on every input.

b) The set of all TM codes for TMs that halt on no input.

c) The set of all TM codes for TMs that halt on at least one input.

* d) The set of all TM codes for TMs that fail to halt on at least one input.