proof of the rice's theorem

Question

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 $<T_∅> \notin P$ without loss of generality, because you could proceed with $\bar{p}$ instead of $P$ if $<T_∅> \in P$.

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

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

$S = $“On input $<M, w>:$

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 $<M_w> \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.

Answer 1

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$.