I have to prove that $H_\varepsilon = \{<M> \mid M\ \text{halts on input }\varepsilon\}$ reduces to $H$ (the halting problem).

I am very confused how to PROVE it, I mean it is clear that we can take a TM $M$ that decides $H$ and then build a TM $M\varepsilon$ that decides $H\varepsilon$ by taking the input $<M1>$ and simulating $M$ on input $(<M1>, \varepsilon)$, then accepting when $M$ accepts.

But how do I prove I can do that, how do I prove that this mapping from $H$ to $H_\varepsilon$ exists?

  • $\begingroup$ Are you sure you want to reduce $H$ to $H\varepsilon$, not to reduce $H\varepsilon$ to $H$? $\endgroup$ – xskxzr Jun 16 '18 at 17:21

Your Answer

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

Browse other questions tagged or ask your own question.