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$
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$
  • $\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 Nov 15 '17 at 23:58
  • 2
    $\begingroup$ fun fact: the problem $L=L^R$ is already undecidable for context-free grammars. $\endgroup$ – Hendrik Jan Nov 16 '17 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$ – Hans Hüttel Nov 16 '17 at 8:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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