# proof of the rice's theorem

Let $$P$$ be any nontrivial property of the language of a Turing machine. Prove that the problem of determining whether a given TM’s language has property $$P$$ is undecidable.

Proof:(This is from sipser's book).

Assume for the sake of contradiction that $$P$$ is a decidable language satisfying the properties and let $$R_P$$ be the TM that decides $$P$$.

We show how to decide $$A_{TM}$$ using $$R_P$$ by constructing TM $$S$$.

First let $$T_∅$$ be a TM that always rejects, so $$L(T_∅)$$ = ∅.

You may assume that $$ \notin P$$ without loss of generality, because you could proceed with $$\bar{p}$$ instead of $$P$$ if $$ \in P$$.

Because $$P$$ is not trivial, there exists a TM $$T$$ with $$ \in P$$.

Design $$S$$ to decide $$A_{TM}$$ using $$R_P$$ ’s ability to distinguish between $$T_∅$$ and $$T$$.

$$S =$$“On input $$:$$

1. Use $$M$$ and $$w$$ to construct the following TM $$M_w$$.

$$M_w$$ = “On input $$x:$$

1. Simulate $$M$$ on $$w$$. If it halts and rejects, reject. If it accepts, proceed to stage $$2$$.
2. Simulate $$T$$ on $$x$$. If it accepts, accept.”
2. Use TM $$R_P$$ to determine whether $$ \in P$$. If YES, accept. If NO, reject.”

TM $$M_w$$ simulates $$T$$ if $$M$$ accepts $$w$$. Hence $$L(M_w)$$ equals $$L(T)$$ if $$M$$ accepts $$w$$ and $$∅$$ otherwise.

Question: I'm having trouble understanding the last few lines of this proof. $$R_p$$ is a decider that decides $$p$$. It tells us that a machine has the property $$p$$ or not. When we run $$R_p$$ on the description of $$M_w$$ and suppose $$M_w$$ accepts $$w$$ then the language of $$M_w$$ equals the language $$T$$ otherwise $$\phi$$. Now i don't understand how this proves that acceptance problem is also solvable if we have a decide for $$P$$. I'm stucked at his point , any help would be great.

## 1 Answer

Let us verify that $$S$$ is a decider for $$A_{\text{TM}} = \{⟨M,w⟩\mid M \text{ is a TM and }M\text{ accepts } w\}$$.

Let $$⟨M,w⟩\in A_{\text{TM}}$$ be the input to $$S$$. Let us see how $$S$$ runs according to its specification.

1. First, construc $$M_w$$. Since $$M$$ accepts $$w$$, $$M_w$$ simulate $$T$$.
2. Use TM $$R_P$$ to determine whether $$⟨M_w⟩ \in P$$. Since $$M_w$$ simulate $$T$$, $$⟨M_w⟩\in P$$. So, the answer is YES. So, accept.

Now let $$⟨M,w⟩\not\in A_{\text{TM}}$$ be the input to $$S$$. Let us see how $$S$$ runs according to its specification.

1. First, construc $$M_w$$. Since $$M$$ do not accept $$w$$, $$M_w$$ simulate $$T_\emptyset$$.
2. Use TM $$R_P$$ to determine whether $$⟨M_w⟩ \in P$$. Since $$M_w$$ simulate $$T_\emptyset$$, $$⟨M_w⟩\not\in P$$. So, the answer is NO. So, reject.

The above analysis shows that $$S$$ is a decider for $$A_{\text{TM}}$$.

Hope this helps.

Exercise of a minute or less. Verify that if $$M$$ do not accept $$w$$, $$M_w$$ simulate $$T_\emptyset$$.