# Proving that it is undecidable if a Turing machine accepts a language that is its own reverse

I have a Turing machine M. How can I prove that $L(M) = (L(M))^R$ is decidable by constructing a Turing machine that can do this? I know how to figure out if two DFA's accept the same language (using the symmetric difference) however I don't believe it works for Turing machines. Now I am able to design a Turing machine where, for a string w, I can determine whether or not the reverse of w is also accepted by the language. The problem is that I'm having trouble determining if the set of all strings is the same as the set of all reverse strings. If I design another TM then I feel like it's just going to infinitely loop. So how can I prove that this is decidable?

The decision problem

Given Turing machine $M$, is $L(M) = (L(M))^R$?

is undecidable. This is a simple consequence of Rice's theorem.

The property (i.e. class of Turing-recognizable languages)

$$\mathcal{S}_{\mathrm{rev}} = \{ L \mid L \; \text{recognizable and } L = L^R \}$$

is non-trivial, since $\emptyset \in \mathcal{S}_{\mathrm{rev}}$ and $\{ ab \} \notin \mathcal{S}_{\mathrm{rev}}$.

• Just to be 100% clear so I'm given a Turing machine M and the question is does (L(M))^R = L(M) where (L(M))^R is the reverse of each string in the language. Is it undecidable because we're working with Turing machines? – Josh Susa Nov 15 '17 at 23:58
• fun fact: the problem $L=L^R$ is already undecidable for context-free grammars. – Hendrik Jan Nov 16 '17 at 0:39
• If you are unhappy with Rice's theorem, here is a reduction from the acceptance problem for Turing machines. Given an instance $\langle M,w \rangle$, build a description of the machine $M'$ whose behaviour is On input $x$: " 1. If $x=ba$ then accept 2. If $x=ab$ then simulate $M$ on $w$ and if $M$ accepts, then accept, else if $M$ rejects, then reject 3. Otherwise, reject" We have that $L(M') = (L(M'))^R$ if and only if $M$ accepts $w$. – Hans Hüttel Nov 16 '17 at 8:32