3
$\begingroup$

I want to find out whether, assuming a language $L_1$ being mapping reducible (i.e., $L_1$ maps to $L_2$ and the complement of $L_1$ maps to the complement of $L_2$) to a language $L_2$ and $L_2$ being recursively enumerable, $L_1$ is recursive or not.

I tried creating a recursive Turing machine for $L_1$ by using the recursively enumerable machine of $L_2$, but if the input belongs to the complement of $L_1$, its mapping will also be in the complement of $L_2$ and we cannot say anything about it.

So I tried proving by contradiction instead: Assuming $L_1$ is recursive, show that our assumption that $L_2$ is recursively enumerable is wrong. However, this will require an inverse mapping. Alternatively, we could also try assuming $L_1$ is recursive and show that such a mapping cannot exist, but I can't think of any approach to it.

Can someone help me?

Mapping reducibility of two languages $L_1$ and $L_2$ is defined as a function which, when given a string in $L_1$, gives as output a string in $L_2$ and, when given as input a string in $L_1$ complement, gives as output a string in $L_2$ complement.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ Do you mean for $L_2$ to be recursively enumerable but not recursive? Remember that all recursive languages are also RE. $\endgroup$
    – David Richerby
    Commented Aug 27, 2016 at 10:28
  • 1
    $\begingroup$ Also, you can use LaTeX here to typeset mathematics in a more readable way. See here for a short introduction. $\endgroup$
    – David Richerby
    Commented Aug 27, 2016 at 10:29
  • $\begingroup$ Thanks for response. If L2 is recursive, the statement is true and can be proved easily, however it's also possible from the problem statement that L2 is recursively enumerable, but not recursive so we need to show that case as well. $\endgroup$
    – user40647
    Commented Aug 28, 2016 at 16:56

1 Answer 1

Reset to default
2
$\begingroup$

If $L_1 \le_m L_2$, that is, $L_1$ is many-one (i.e., mapping) reducible to $L_2$ and $L_2$ is recursively enumerable (r.e.), then $L_1$ must also be r.e. This is because an acceptor for $L_1$ can be derived by reducing any instance $w$ of $L_1$ to an instance $w'$ of $L_2$ and then simulating the acceptor for $L_2$ (which exists on grounds of $L_2$ being r.e.) on $w'$.

However, in general, $L_1$ does not have to be recursive (which is strictly stronger than r.e.). In fact, any language $L$ is (trivially) many-one reducible to itself, so just take your favorite r.e. but not recursive language $L$ and note that $L \le_m L$ holds despite $L$ not being recursive.

Honestly, I believe your confusion arises from your unnecessarily complex view of many-one reducibility (i.e, on the basis of $L_1$, $L_2$, and their complements). Note that you can think of a reduction of $L_1$ to $L_2$ instead as mapping any instance $w$ of $L_1$ to an instance $w'$ of $L_2$ under the condition $w \in L_1 \iff w' \in L_2$. Stating this based on the equivalence sign "$\iff$" avoids having to think about the complements of $L_1$ and $L_2$, thus avoiding unnecessary "clutter" in your thought process.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.