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.

  • 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 Aug 27 '16 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 Aug 27 '16 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 Aug 28 '16 at 16:56

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.


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.