سؤال

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.

لا يوجد حل صحيح

مرخصة بموجب: CC-BY-SA مع الإسناد
لا تنتمي إلى cs.stackexchange
scroll top