# 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$$. $$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. Posted on Categories proxies