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.

  • 1
    $\begingroup$ Thank you for your answer! $\endgroup$ – Foghunt Jun 16 '20 at 15:22

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.