I came across the following example that proves that the blank tape halting problem is not decidable.

I understand the proof technique, but I just don't see how the blank tape problem is shown to be undecidable in the proof.

It says $M_{w}$ starts with a blank tape but then writes $w$ onto the tape, so there is no difference to the general halting problem.

How does this imply that the blank tape halting problem is not decidable? I can't find the logical conclusion. Couldn't we just replace the blank tape halting problem with another DECIDABLE problem and argue the same way?


closed as unclear what you're asking by Tom van der Zanden, Evil, sashas, David Richerby, Gilles Nov 29 '15 at 21:01

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 3
    $\begingroup$ Please don't use images as main content of your post. This makes your question impossible to search and inaccessible to the visually impaired; we don't like that. Please transcribe text and mathematics (note that you can use LaTeX) and don't forget to give proper attribution to your sources! $\endgroup$ – D.W. Nov 25 '15 at 18:54
  • $\begingroup$ Won't happen again. $\endgroup$ – Javiator Nov 25 '15 at 18:57
  • 2
    $\begingroup$ Please edit it away now. $\endgroup$ – Raphael Nov 25 '15 at 19:16
  • 1
    $\begingroup$ "I understand the proof technique, but I just don't see how [...] is shown [...] in the proof." -- This sentence seems self-contradictory to me. Note that this is a proof sketch. Flesh out the details to see clearer. $\endgroup$ – Raphael Nov 25 '15 at 19:18
  • $\begingroup$ This seems more a logic issue than a computer science one. If A implies B and B is false than you can deduce that A is false. A can be true only if B is also true does not mean that if B is true you can deduce that A is true. (A is "the blank tape problem is decidable", B is "the halting problem is decidable"). $\endgroup$ – AProgrammer Nov 26 '15 at 10:48

The argument shows that if you can solve the blank tape halting problem then you can solve the halting problem. Since you can't solve the halting problem, it follows that you can't solve the blank tape halting problem. (Here "solve" means "decide with a program that always halts".)

It's true that the same argument shows that many other problems are undecidable. But if you try to prove that a decidable problem is undecidable this way, then something will go wrong. Try it out!


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