# Correct approach to Mapping Reduction from $E_{TM}$

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

• $L = \{x : x \not= x^R \}$ verifies $L = L^R$... hence this reduction doesn't work. – Tpecatte Sep 7 '13 at 19:33
• 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^{*}$ – gr1ph00n Sep 7 '13 at 21:46