1
$\begingroup$

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?

$\endgroup$
0
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – user79943 Nov 10 '17 at 20:04
  • $\begingroup$ @Wen A problem $L$ is r.e. IFF $L \leq_m HALT$. It is exactly equivalent, so it does not imply anything else. $\endgroup$ – chi Nov 10 '17 at 20:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy