1
$\begingroup$

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?

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

1 Answer 1

1
$\begingroup$

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 $<M,x>$ 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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.