0
$\begingroup$

I'm trying to show that $L=\{ \langle M \rangle \colon L(M)=L(M)^R\}$ is undecidable, but I don't even know where to begin. Google wasn't much of a help, maybe because it's hard describing the language in words. Any hints?

$\endgroup$
  • 3
    $\begingroup$ Use Rice's theorem. If you don't know what that is, look it up and read the proof. Now you can prove your special case in the very same way. $\endgroup$ – Yuval Filmus Jul 11 '15 at 19:49
  • $\begingroup$ What do you define $L(M)^{R}$ to be? $\endgroup$ – Ryan Jul 11 '15 at 20:28
  • $\begingroup$ Every string in $L(M)^R$ is a reverse of some string in $L(R)$ $\endgroup$ – Yotam Jul 12 '15 at 7:42
  • $\begingroup$ "I don't even know where to begin" -- review your class material, textbooks, and our reference question. "it's hard describing the language in words" -- what about "the set of Turing machines whose languages are closed against reversal"? $\endgroup$ – Raphael Jul 12 '15 at 9:48