1
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.