Is it correct to say L is RE if I can map reduction from LH to L?

Question

I seem to be not understanding correctly what reductions means for Languages.

for example, Lets say there is a Language called LM.

I want to see if LM is recursive or not, to do that lets say I find a reduction from L-Halting problem to LM.

and I assume that LM is recursive, so I show that then L-Halting problem is also recursive, which of course is false therefore LM is not recursive.

but can I say that LM is RE because I found a way to reduce LH to LM? if not how can I show that LM is RE?

Answer 1

Let's clear things a bit, since there are many equivalent/similar definitions that could lead to misunderstandings.

• You can show that a language $L$ is recursive by constructing a recursive function $\chi_L$ (or a Turing machine or any other equivalent computation model) that decides it, i.e. $$\chi_L (x) = \begin{cases} 1 & \quad ; x \in L \\ 0 & \quad ; \text{otw}. \end{cases}$$ notice that $\chi_L$ must be defined for all inputs.

• You can show a that language $L$ is not recursive, by finding a "Turing reduction" from a non-recursive language to it. This is probably what what you mean by reduction, and it is defined as follows:

  We say that a language $A$ is Turing-reducible to a language $B$, written $A \le_T B$, if we can construct a recursive function (or Turing machine) that decides $A$ by assumption that there is such function for $B$.

  As you see by definition, Turing reduction somehow "transfers recursiveness" from $B$ to $A$.

  For any $A$ and $B$ such that $A \leq_T B$, if $B$ is recursive, then so is $A$.

  Hence if we already know that some $A$ is not recursive, then finding a reduction $A \leq_T B$ for any $B$ makes it non-recursive too.

• You can show that a language $L$ is RE, by constructiong a recursive function $\varphi_L$ (or Turing machine) that $Dom(\varphi_L) = L$ (or halts on/accepts it), for example $$\varphi_L(x) = \begin{cases} 1 & \quad ; x \in L \\ \uparrow & \quad ; \text{otw.} \end{cases}$$

  where $\uparrow$ means "not defined" (or "does not halt"). There are other definitions of RE-ness, like its namesake "enumerability", which you can easily observe that are equivalent to this one.

• But in showing a language $L$ is not RE, Turing reduction does not help, since it does not necessarily transfer RE-ness. For example observe that $\overline{L_{HALT}} \leq_T L_{HALT}$ (indeed any language is Turing-reducible to it's complement and vice versa), but we know that $L_{HALT}$ is RE, while $\overline{L_{HALT}}$ is not.

  But there are other kinds of stronger reduction that do transfer RE-ness. One such reduction is called "many-one redicibility":

  We say that a language $A$ is many-one-reducible to a language $B$, written $A \leq_m B$, if there is a total recursive function $f$ such that for any input $x$ $$x \in A \iff f(x) \in B$$

  This is a stronger reduction in the sense that $A \leq_m B$ implies $A \leq_T B$ (and not necessarily vice versa). So, like Turing reduction, it transfers recursiveness. We also have

  For any $A$ and $B$ such that $A \leq_m B$, if $B$ is RE, then so is $A$.

  To see how this is true, just take $\varphi_A(x) = \varphi_B(f(x))$.

  Hence the correct method to show a language $B$ is not RE, is to find a many-one reduction $A \leq_m B$ for some non-RE language $A$. Notice that the above example does not work here, because $\overline{L_{HALT}} \nleq_m L_{HALT}$.

For further reading, see Computability Theory by S. Barry Cooper Pt. I, Ch. 7.