1
$\begingroup$

If $L_1,\, L_2 \in RE / R$, must there exist a (computable) many-one reduction between them?

I can prove that for every two languages in $R$ exists a reduction between them. A possible reduction $L_3 \leq L_4$ where $L_3,\, L_4\in R$ goes as follows:

given an input $x$ to $L_3$, run $M_3$ (it's TM), if it accepted, return an input that is in $L_4$. Else, return one that isn't (this works assuming $L_4\neq \emptyset,\, \Sigma^*$).

The above idea will not work in $RE$ because $M_3$ might not halt.

Is there a different way to construct a reduction $L_1\leq L_2$ where it us known that $L_1,\, L_2\in RE / R$? Or is such a general reduction something that cannot be always achieved?

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ The halting problem and the evenness problem (checking whether the input is even) are both RE. Can you reduce one to the other? $\endgroup$
    – chi
    Feb 4 '17 at 20:18
  • $\begingroup$ Is the evenness problem defined $L_{even}=\{<M_1> <M_2>\, |\,\, L(M_1)=L(M_2)\}$? If so, a reduction between $L_{halt}\leq L_{even}$ will be given a $<M><w>$ to construct a new TM $N_1$ s.t. for every input $x$ the TM $N_1$ runs $M$ on $w$ for $|x|$ steps. If $M$ accepted/rejected during these $|x|$ steps, then $N_1$ will accept $x$. The TM $N_2$ will be similiar, just that it will first check $x=\varepsilon$? If yes, it will accept. Otherwise, it will run $M$ on $w$ for $|x|$ steps and same as $N_1$. This way, the languages will be the same if $M$ halts on $w$ and different if not. $\endgroup$
    – Eric_
    Feb 4 '17 at 20:29
  • $\begingroup$ So, in order to not compare apples and oranges, shouldn't you talk about RE-complete problems? $\endgroup$
    – Raphael ♦
    Feb 4 '17 at 21:00
  • $\begingroup$ I think my remark about $NP-Complete$ is less meaningful, I am more curious in regards to two languages in $RE$. $\endgroup$
    – Eric_
    Feb 4 '17 at 21:46
  • $\begingroup$ @Eric_ No, I was talking about the set of even naturals, which is RE (it is also R). And no reduction can exist between the halting problem to it, since the halting problem is not R. I think the real interesting question is, are any two languages RE but not R reducible between them? (I think the theory of m-degrees answered that positively: there are degrees between 0 and 0') $\endgroup$
    – chi
    Feb 5 '17 at 9:56
1
$\begingroup$

Consider the case $L_2 = \emptyset$. This language is clearly recursively enumerable, but the only language which can be reduced to it is itself.

What is true, and follows directly from the definition, that two RE-complete languages reduce to one another.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Yes, I have stated that $L_3 \leq L_4$ for every $L_3,\, L_4\in R$ apart from $L_4 =\emptyset,\, \Sigma^*$. Same for $RE$, I'm curious to know if every two languages in $RE$ (apart from $\Sigma^*$ and $\emptyset$) can be reduced to one another. $\endgroup$
    – Eric_
    Feb 5 '17 at 8:01
  • $\begingroup$ This also isn't true. Take for example $L_2$ to be any recursive language. $\endgroup$
    – Yuval Filmus
    Feb 5 '17 at 9:03
  • $\begingroup$ I see. I will re-edit my question accordingly. $\endgroup$
    – Eric_
    Feb 5 '17 at 19:41
  • 1
    $\begingroup$ The answer to your updated question is still no. See for example Wikipedia. $\endgroup$
    – Yuval Filmus
    Feb 5 '17 at 19:48

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.