1
$\begingroup$

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?

$\endgroup$

1 Answer 1

4
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$
    – Josh Susa
    Commented Nov 15, 2017 at 23:58
  • 2
    $\begingroup$ fun fact: the problem $L=L^R$ is already undecidable for context-free grammars. $\endgroup$ Commented Nov 16, 2017 at 0:39
  • 1
    $\begingroup$ 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$. $\endgroup$ Commented Nov 16, 2017 at 8:32

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.