0
$\begingroup$

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?

$\endgroup$
8
  • $\begingroup$ Turing machines have an infinitely long tape, is there some way given an input word w, you could obtain the word in reverse order? $\endgroup$
    – awillia91
    Mar 16, 2021 at 14:15
  • $\begingroup$ 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. $\endgroup$ Mar 16, 2021 at 14:20
  • $\begingroup$ The dollar sign would of course also be erased at the end. (Used the dollar sign simpluy to separate the original and reversed string). $\endgroup$ Mar 16, 2021 at 14:21
  • $\begingroup$ 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? $\endgroup$
    – awillia91
    Mar 16, 2021 at 14:24
  • $\begingroup$ 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. $\endgroup$
    – awillia91
    Mar 16, 2021 at 14:38

2 Answers 2

2
$\begingroup$

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$.

$\endgroup$
1
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.