Problem Detail: 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
