# Confusion about reduction of $L=\{w_i | M_i\text{ halts on }w_i\}$ to Halting Problem or Diagonalization language?

I want to reduce $L$ (stated above) to the Halting Problem in order to say that L is recursively enumerable but not recursive just like the Halting Problem, but is it enough to say that if I can solve the Halting Problem then I can solve $L$, because then I can feed into the Halting Problem the input $w_i$ twice, as both input and Turing machine encoding?

Do I need to reduce it to the diagonalization language instead?

I want to reduce $L$ (stated above) to the Halting Problem in order to say that L is recursively enumerable

So far, so good.

but not recursive just like the Halting Problem

Here we have a problem. Reducing $L \leq_m HALT$ does not prove that $L$ is not recursive. Actually, all recursive languages reduce to $HALT$!

but is it enough to say that if I can solve the Halting Problem then I can solve $L$

No, this is not a may-one reduction argument. Indeed, if you can solve $HALT$, then you can also solve its complement. This however, does not imply that the complement is r.e., otherwise we would get that $HALT$ is recursive.

You need to define a (total recursive) reduction function from $L$ to $HALT$.

Then you need to prove that $L$ is not recursive. For that, you could prove the opposite direction $HALT \leq_m L$, constructing a reduction function from $HALT$ to $L$.

• Oh okay, so if I reduce L to the Halting Problem that only says that L is recursively enumerable like the Halting Problem but says nothing more specific about L?
– user79943
Nov 10, 2017 at 20:04
• @Wen A problem $L$ is r.e. IFF $L \leq_m HALT$. It is exactly equivalent, so it does not imply anything else.
– chi
Nov 10, 2017 at 20:55