1
$\begingroup$

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 :

enter image description here

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.

Improve this question
$\endgroup$
  • 1
    $\begingroup$ You should define in your post the Blank-tape problem for completeness. $\endgroup$ – fade2black Jan 5 '18 at 21:06
  • $\begingroup$ 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. $\endgroup$ – potestasity Jan 5 '18 at 21:27
  • $\begingroup$ Please avoid using pictures, try to describe the reduction in the post to avoid dependency on external resources. $\endgroup$ – Ariel Jan 5 '18 at 21:33
  • $\begingroup$ I will edit my Post after reading the awnsers , thank you. $\endgroup$ – xmen-5 Jan 5 '18 at 21:38
1
$\begingroup$

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.

Improve this answer
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – xmen-5 Jan 5 '18 at 21:44
  • $\begingroup$ 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)$. $\endgroup$ – fade2black Jan 5 '18 at 21:50
  • $\begingroup$ do you mean that the blank tape decider execute M on w and sees if it halts or no ? $\endgroup$ – xmen-5 Jan 5 '18 at 21:56
  • $\begingroup$ 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". $\endgroup$ – fade2black Jan 5 '18 at 22:05
  • $\begingroup$ 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........ $\endgroup$ – xmen-5 Jan 5 '18 at 22:12
1
$\begingroup$

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.

Improve this answer
$\endgroup$
  • $\begingroup$ do you mean by 'simulates the machine M on input w' ---> exuting M on w?is <M> = <Mw>? $\endgroup$ – xmen-5 Jan 5 '18 at 21:37
  • $\begingroup$ 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. $\endgroup$ – Ariel Jan 5 '18 at 21:41
  • $\begingroup$ can i say that Mw is the encoding of M followed by the word w? $\endgroup$ – xmen-5 Jan 5 '18 at 22:01
  • $\begingroup$ 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. $\endgroup$ – Ariel Jan 5 '18 at 22:07
  • $\begingroup$ 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..... $\endgroup$ – xmen-5 Jan 5 '18 at 22:17

Your Answer

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

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