Rice theorem, the proof of the part when the empty language belongs to the property


I was going through the classic text “Introduction to Automata Theory, Languages, and Computation” by Hofcroft, Ullman and Motwani where I came across the proof the Rice theorem as shown.

$ L_u$ => Language accepted by universal turing machine

$ P$ => property of a regular language

$ L_P$ => set containing the codes of the turing machines which accept those languages in $ P$

Theorem : (Rice’s 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 $ \phi$ , the empty language, is not in $ P$ . we shall return later to the opposite case. Since $ P$ is nontrivial, there must be some nonempty language $ L$ that is in $ P$ . Let $ M_L$ be a $ TM$ accepting $ L$ . We shall reduce $ L_u$ to $ L_P$ , thus proving that $ L_P$ is undecidable, since $ L_u$ 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; $ L(M’)$ is $ \phi$ if $ M$ does not accept $ w$ , and $ L(M’)$ = $ L$ if $ M$ accepts $ w$ .

Construction of M' for the proof of Rice's 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 $ w$ 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 $ M_L$ 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. If $ M$ does not accept $ w$ , then $ M’$ does nothing else. $ M’$ never accepts its own input, $ x$ , so $ L(M’) = \phi$ . Since we assume $ \phi$ is not in property $ P$ , that means the code for $ M’$ is not in $ L_P$ .

  2. If $ M$ does not accept $ w$ , then $ M’$ does nothing else. $ M’$ never accepts its own input, $ x$ , so $ L(M’) =\phi$ . Since we assume $ \phi$ is not in property $ P$ , that means the code for $ M’$ is not in $ L_P$ .

  3. If $ M$ accepts $ w$ , then $ M’$ begins simulating $ M_L$ on its own input $ x$ . Thus, $ M’$ will accept exactly the language $ L$ . Since $ L$ is in $ P$ , the code for $ M’$ is in $ L_P$ .

Constructing $ M’$ from $ M$ and $ w$ can be carried out by an algorithm. Since this algorithm turns $ (M,w)$ into an $ M’$ that is in $ L_P$ if and only if $ (M,w)$ is in $ L_u$ , this algorithm is a reduction of $ L_u$ to $ L_P$ , and proves that the property $ P$ is undecidable.

We are not quite done. We need to consider the case where $ \phi$ is in $ P$ . If so, consider the complement property $ \overline P$ , the set of $ RE$ languages that do not have property $ P$ . By the foregoing, $ \overline P$ is undecidable. However, since every $ TM$ accepts an $ RE$ language, $ \overline {L_P}$ , the set of (codes for) Turing machines that do not accept a language in P is the same as $ L_{\overline P}$ , the set of TM’s that accept a language in $ \overline P$ . Suppose $ L_P$ were decidable. Then so would be $ \overline {L_P}$ , because the complement of a recursive language is recursive.

I could not understand the last paragraph in bold.