Prove that the set of Turing-decidable languages are closed under reversal.

663 Views Asked by At

I.e., prove if $L$ is Turing-decidable, then $L^ℛ=\{x\in\Sigma^* | x^ℛ\in L, \text{ where }x^ℛ\text{ is the reverse of }x\}$ is Turing-decidable. I know that the statement is true, but struggling with how to prove it formally.

1

There are 1 best solutions below

1
On BEST ANSWER

If $L$ is decidable, then we can decide $x \in L^{\mathscr{R}}$ by reversing $x$ and checking if the result is in $L$.