reducing the halting problem to the blank tape problem

Question

I have checked many discussions for understanding this problem.

I understand the reasoning , unfortunately there are some drawback in my understanding.

The Blank-tape halting Problem

Input: Turing Machine M

Question : Does M halt when started with a blank tape?

So this is the reduction :

The construction of Mw is as follows :

• When started on blank tape, writes w
• Then continues execution like M

What i don't undesstand is the step 2 , in my opinion if we execute M on w maybe M will loop !!!

My second question : what the blank-tape do when executed?even if the blanktape machine halt on blank tape , how can we be sure that M halt on w .i miss something here.

Thank you in advance.

Answer 1

The Blank-tape Halting problem, given a Turing machine $\langle M \rangle$, asks whether or not $M$ eventually halts when starts from the empty tape, i.e, its input is the empty string.

It is a decision problem that returns "YES" or "NO". Thus the decider for the Blank-tape Halting problem is another Turing machine $M_{D}$ that takes as input a Turing machine $\langle M \rangle$ (its description) and returns "YES" or "NO" (prints "YES" or "NO" and halts).

Reducing the Halting problem to the Blank-tape Halting problem means that the we should construct a decider for the Halting problem using the decider for the Blank-tape Halting problem. We could construct it as following.

HP-decider(M,w)
  1) generate a TM M' which starts from the empty tape
     then writes w on its tape and runs on w
  2) result = BTHP-decider(M')
  3) if result == "YES" then return YES
  4) if result == "NO" then return NO 
end

It is not hard to see that $M'$ halts iff $M(w)$ halts.

In fact you don't need to simulate $M$ on $w$. You don't care about how BTHP-decider(M') works/decides either. What you must show is that the Halting problem is solvable using the Blank-tape Halting problem.

Answer 2

The reduction does not actually execute $M$, what its actually doing is the following mapping:

$\big(\langle M\rangle,w\big)\mapsto \langle M_w\rangle$

Where $M_w$ is the machine that when executed with blank tape, simulates the machine $M$ on input $w$. Preforming the reduction does not require that you execute $M$, you simply need to write down the code of $M_w$. Obviously $M$ halts on $w$ iff $M_w$ halts when executed with blank tape (we constructed $M_w$ specifically for this purpose), and the correctness of the reduction follows.