0
$\begingroup$

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

$\endgroup$
7
  • 1
    $\begingroup$ 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.) $\endgroup$ – Raphael Jun 15 '15 at 11:08
  • $\begingroup$ 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? $\endgroup$ – Lee Jun 15 '15 at 11:44
  • $\begingroup$ It's the most simple functions that admits the equivalence you state. Hint: the image of $f$ has size two. $\endgroup$ – Raphael Jun 15 '15 at 12:53
  • $\begingroup$ While this question asks for more than yours does, the answers contain the answer to your question. $\endgroup$ – Rick Decker Jun 15 '15 at 15:16
  • $\begingroup$ @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..?) $\endgroup$ – Lee Jun 15 '15 at 19:21