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

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?

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.

• Thank you for your answer! – Foghunt Jun 16 '20 at 15:22