# Proving that Turing decidable languages are closed under reversal

I need to prove that Turing decidable languages are closed under reversal. I have no idea on how I would prove this. Any suggestions or clues?

• Turing machines have an infinitely long tape, is there some way given an input word w, you could obtain the word in reverse order? Mar 16, 2021 at 14:15
• Yes. Move to the last character of the string, place a dollar sign after it, go back and write the characters from the last to the first one and replace the original string with blanks. Mar 16, 2021 at 14:20
• The dollar sign would of course also be erased at the end. (Used the dollar sign simpluy to separate the original and reversed string). Mar 16, 2021 at 14:21
• Now notice that reversing a word twice recovers the original word. Then can we use the decider for a language L to determine if a word is the reverse of a word in L? Mar 16, 2021 at 14:24
• Also note that formally we must determine if the reversed word is in L or not which I neglected to say in my previous comment. This is not an issue since we assume we have a decider for L. Mar 16, 2021 at 14:38

Let $$L$$ be a decidable language and let $$M$$ be a decider for $$L$$. Since $$M$$ decides $$L$$, $$M$$ always halts and accepts if its input is in $$L$$ and rejects if its input is not in $$L$$.

We know that string reversal can be performed by a Turing machine. Let's construct a Turing machine to decide if a word is in $$L^r=\{w=w_0w_1...w_n \mid w^r=w_nw_{n-1}...w_0\in L\}$$.

Let $$M'$$ = "On input $$w$$
$$\quad$$reverse the string $$w$$ to obtain $$w^r$$
$$\quad$$run $$M$$ on $$w^r$$
$$\quad$$if $$M$$ accepts, $$ACCEPT$$
$$\quad$$otherwise, $$REJECT$$ "

Then $$M'$$ accepts $$w$$ if and only if $$M$$ accepts $$w$$. Since $$M$$ is a decider, both machines always halt. Then $$M'$$ decides $$L^r$$.

Suppose that you have a Turing machine $$M$$ that accepts a language $$L$$.

Construct a new Turing machine which, on input $$x$$, reverses its input and then passes control to $$M$$. The new Turing machine accepts the reverse of $$L$$.