patternMinor
Mapping reducibility from recursive to recursively enumerable language
Viewed 0 times
recursivelyreducibilityenumerablerecursivelanguagemappingfrom
Problem
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.
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.
Solution
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.
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.
Context
StackExchange Computer Science Q#62925, answer score: 2
Revisions (0)
No revisions yet.