# mapping reduction for every recursive language [duplicate]

how do I prove that for every 2 languages $A,B\in R$ where $A,B \notin \{ \emptyset , \Sigma^* \}$

I can do a reduction $A \leq_m B$?

[EDIT] My try:

$A$ is decidable therefore it has a turing machine that decides it - $T_A$

For every x, we can check whether $T_A$ accepts x or not, if it accepts then we run over the alphabet and try to find words that are in B.

$B \notin \{ \emptyset , \Sigma^* \}$ therefore there exists words that are in B and words that are not.

if $T_A$ accepts x then we return a word that we found that is in B else if x is not in A then we return a word that is not in B.

This can be done only because $A,B \notin \{ \emptyset , \Sigma^* \}$ And because A and B are decidable

• Look closely at the definition of mapping reduction. There is not much more to it than that. (I know we have answered that for NP and poly-time many-one reductions before, but I can't find it. The answer is pretty much the same.) – Raphael Jun 15 '15 at 11:08
• If it is provable then according to the definition $x \in A \leftrightarrow f(x)\in B$, there must exist some "generic" function that converts every problem in R to every other problem in R. Can you point me to how to think about that function? – Lee Jun 15 '15 at 11:44
• It's the most simple functions that admits the equivalence you state. Hint: the image of $f$ has size two. – Raphael Jun 15 '15 at 12:53
• While this question asks for more than yours does, the answers contain the answer to your question. – Rick Decker Jun 15 '15 at 15:16
• @Raphael So it is just a function that runs the turing machine of B on x and return the answer? (Because $B \in R$ then its turing machine is decidable therefore we can run it in a computable function..?) – Lee Jun 15 '15 at 19:21