So we can prove that the language say $A = \{ \langle M,w \rangle \mid \text{M is TM that accepts } w^R \text{ whenever it accepts } w \}$ is undecidable by assuming it is decidable and use that to construct a $TM$ deciding $A_{TM}$. So by contradiction $A$ is undecidable. But what if the language was $\{ \langle M,w \rangle \mid \text{M accepts } w \text{ but on input } w^R \text{halts and rejects} \}$?
I was thinking to prove that it's r.e, we can construct a Turing recognizer, say $K$, which recognizes this language by simulating $M$ on $w$ and do whatever $M$ does. But how does the machine know what's $w$ and $w^R$? Non determinism maybe? Or am I looking at it the wrong way?
And to prove that it's undecidable would we use the same approach as that for $A$?
Asked By : muddy
Answered By : A.Schulz
Let $ A = \{\langle M, w \rangle \mid M \text { is a TM, } M \text { accepts } w \text { and on input } w^R \text { halts and rejects} \} $.
We prove that $A$ is not decidable by showing $\text{HALT}\le_m A$. The reduction works as follows. Let $\langle M, w \rangle $ be an instance of $\text{HALT}$, then we construct a Turing machine $M'$ based on $M$ and $w$. Let $M_{01}$ be some TM that accepts $01$ and rejects all other inputs. The TM $M'$ on input $v$ works now as follows
- $M'$ simulates $M(w)$
- When the simulation is finished simulate $M_{01}(v)$ and return the result of the simulation
The reduction maps $\langle M, w \rangle$ to $\langle M', 01 \rangle$.
We have now $$ \begin{align} \langle M, w \rangle \not \in \text{HALT} & \Rightarrow M' \text{cycles on every input} \\ & \Rightarrow \langle M', 01 \rangle \not \in A \end{align} $$ and \begin{align} \langle M, w \rangle \in \text{HALT} & \Rightarrow M' \text{acts as } M_{01} \\ & \Rightarrow M' \text{ accepts } 01 \text{ and rejects } 10\\ & \Rightarrow \langle M', 01 \rangle \in A \end{align}
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/7285
0 comments:
Post a Comment
Let us know your responses and feedback