1
$\begingroup$

as the title states, I am trying to figure out if my approach to solving mapping reduction from $E_{TM}$ to some other language is correct. As you surely know, $E_{TM} = \left \{ < M> \mid M \ is \ a \ TM \ such \ that \ L(M)= \emptyset \right \} $. What i am trying to check is whatever a string x is in L(M). My idea is to analyse $<M>$ in oder to check if there are any transition to $q_{accept}$, if so then L(M) cannot be empty. Now let's take another language, for instance let $REVERSE_{TM} = \left \{< M> \mid M \ is \ a \ TM \ such \ that \ L(M) = L(M)^{R} \right \} $ or even $REGULAR_{TM} = \left \{< M> \mid M \ is \ a \ TM \ such \ that \ L(M) \ is \ regular \right \} $. Let's prove that $E_{TM} \leq_{m} REVERSE_{TM} $. Since i need to convert an istance "yes" w of $E_{TM}$ trought a function f, to f(w) which is an instance "yes" of $REVERSE_{TM}$. $f(<M>) = <M^{'}>$, where $<M^{'}>$ is a TM whose behaviour on input x is

  1. if $x \neq x^{R}$ then accept.

  2. if $x = x^{R}$ then,

    • analyse $<M>$ and if there are no transitions to $q_{accept}$ then accept

    • else do not accept x

Which language does M' recognize? It should recognize $ \Sigma^{*} $ if $L(M) = \emptyset $ meanwhile it should match $ \left \{ x \in \Sigma^{*} \mid x \neq x^{R} \right \} $. We know that $(\Sigma^{*})^{R} = \Sigma^{*}$, so $<M'> \in REVERSE_{TM} <=> L(M) = \emptyset$. I think this mapping reduction should be correct but is it correct to let M' analyse M in order to figure out if L(M) is really empty (if it's empty there should be no transition to $q_{accept}$) ? Or is there another way to solve these reduction from $E_{TM}$ ?

$\endgroup$
  • $\begingroup$ $L = \{x : x \not= x^R \}$ verifies $L = L^R$... hence this reduction doesn't work. $\endgroup$ – Tpecatte Sep 7 '13 at 19:33
  • $\begingroup$ Yes Timot thanks, You are right, I was too keen on the transitions checking that I did not consider that aspect, however i might try to check if $x \in \left \{ 0^{n}1^{n} \right \}$ and then accept. So that it should recognise either $ \left \{ 0^{n}1^{n} \mid n \in N \right \} $ or $\Sigma^{*}$ $\endgroup$ – gr1ph00n Sep 7 '13 at 21:46

Your Answer

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

Browse other questions tagged or ask your own question.