This question already has an answer here:

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?


marked as duplicate by Raphael Jul 12 '15 at 9:46

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 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