# Prove that $H$ reduces to $H\varepsilon$

I have to prove that $$H_\varepsilon = \{ \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 $$$$ and simulating $$M$$ on input $$(, \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?

• Are you sure you want to reduce $H$ to $H\varepsilon$, not to reduce $H\varepsilon$ to $H$? Commented Jun 16, 2018 at 17:21

This can be done by hard-coding a pre-processing stage to paste down $$x$$ to the input tape, before actually running $$M$$ on $$x$$ as input.
So given an instance $$$$ of HALTING, you transform $$M$$ to $$M_x$$ that submerges the input $$x$$ into its initial stage. This can be done efficiently.
For example, if $$x=010$$, then start from the starting state $$q$$ of $$M_x$$ at left-marker $$\$$, it moves one step to the right, and changes to state $$q_0$$. Then, $$M_x$$ prints out $$0$$, moves the head one step to the right and changes to state $$q_1$$. Then, $$M_x$$ prints out $$1$$, moves the head one step to the right and changes to state $$q_2$$. Then, $$M_x$$ prints out $$0$$, moves the head one step to the right and changes to state $$q_3$$. Then, $$M_x$$ moves all the way left back to the left-marker $$\$$. Then, $$M_x$$ changes to the very starting state $$q_M$$ of $$M$$ and passes the control to $$M$$. Now, $$M$$ receives $$x$$ as input on the tape.
The above behavior of $$M_x$$ should be coded as its transition table. The description of $$M_x$$ is the produced instance of $$H_\varepsilon$$.
Finally, $$M$$ halts on $$x$$ iff. $$M_x$$ halts on $$\varepsilon$$.