# reducing the halting problem to the blank tape problem

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.

• You should define in your post the Blank-tape problem for completeness. Jan 5 '18 at 21:06
• The "blank-tape halting problem decider" is something which you assume to exist, capable of always providing the correct YES/NO answer. The transformation should make it so that $M_w$ halts on the blank tape if and only if $M$ halts on $w$, i.e. these problems become equivalent. Your drawing shows how this gives you a halting problem decider, which you know doesn't exist. Thus you've reached a contradiction, so the assumption was wrong and the blank-tape decider doesn't exist either. Jan 5 '18 at 21:27
• Please avoid using pictures, try to describe the reduction in the post to avoid dependency on external resources. Jan 5 '18 at 21:33
• I will edit my Post after reading the awnsers , thank you. Jan 5 '18 at 21:38

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.

• 3) if result == "YES" means that M' halt on empty tape . i don't understand how we can deduce from here that M halt on w.sorry but a lot of confusion in my head. Jan 5 '18 at 21:44
• Yes, result == "YES" means that M' halts on empty tape. BTHP-decider(M') decides whether or not $M'$ halts. ($M'$ is $M_w$ in your post). What does $M'$ ( or $M_w$) do? It starts from the empty tape and writes down "its own input $w$" and then runs on $w$, kind of $M(w)$. Jan 5 '18 at 21:50
• do you mean that the blank tape decider execute M on w and sees if it halts or no ? Jan 5 '18 at 21:56
• Not exactly. It decides if $M'$ (or $M_w$) halts. But $M_w$ halts iff $M(w)$ halts, since what $M_w$ does is starts from the empty tape, writes $w$ on the tape and runs on $w$ equivalently to $M(w)$. But we do not know how the empty blank halting problem decider works, and in fact we don't care about it. What is important its response: "YES" or "NO". Jan 5 '18 at 22:05
• So the key idea is M' , its execution is starting from empty input , writing w on its tape , and execute . as the decider get M' with the blank tape it can decide that our M' halt or not........ Jan 5 '18 at 22:12

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.

• do you mean by 'simulates the machine M on input w' ---> exuting M on w?is <M> = <Mw>? Jan 5 '18 at 21:37
• Yes to the first question, the term simulation is often used when we talk about a new computation which mimics some other given computation, e.g. a Universal Turing machine is able to execute (simulate) any given machine. $\langle M\rangle$ is a notation for the encoding of the machine $M$, since $M$ and $M_w$ are different machines, they have different encodings. Jan 5 '18 at 21:41
• can i say that Mw is the encoding of M followed by the word w? Jan 5 '18 at 22:01
• No. $M_w$ is a new machine, which has $M,w$ hardcoded into it. This is analogous to having a new function $g$ in your favorite programming language using the code of some other function $f$. I suggest that you go over the basics again, perhaps by following some book/course notes, and review your question again after you have done so. Jan 5 '18 at 22:07
• thank you ariel , next week i will have an exam , unfortunatly this part is very hard for me , i'm trying to understand some problem.thank you very much , i think i get the trick..... Jan 5 '18 at 22:17