How does reducing the Halting problem prove the reduction cannot exist?

Question

For example, take the problem "Does M Halt on the Blank Tape?".

My approach was to reduce the halting problem to prove this problem is also undecidable. I generated a Mw by

1. Writing w on the tape
2. Moving to the leftmost blank
3. Running M

Then, of course there is the M-halt-on-blank function:

if(Mw halts)
    true
else false

Where I am having difficulty is understanding how this "proves" the halting problem. The halting problem is supposed to take in an input w and a machine M and tell if M halts on w. If we are creating Mw by taking w and modifying it, and running M on the modified tape, then M isn't really running on w at all. Instead, it is running on this modified tape. This would mean there is an infinite amount of w's that cannot even be run on M. So by using M-halt-on-blank as a decider, how is that solving the halting problem, and thus proving itself to be undecidable?

I understand there are a few similar posts but I am more concerned with the ends than the means for this problem, and I didn't find previous posts to answer this.

Answer 1

First, I think you're confused about some terminology.

• You don't "prove the halting problem". In computer science, problems are computational tasks: you don't prove tasks; you perform them. Or, in this case, you you prove that there is no algorithm that decides the halting problem.

• You don't "reduce the halting problem". A reduction is a conversion between two problems so, when you talk about reductions, you need to say what you're reducing from and what you're reducing to.

Second, you've confused which way this reduction is going. You're trying to prove that the blank-tape halting problem is undecidable, and you do this by proving that a problem that is known to be undecidable (in this case, the halting problem) reduces to it. That is, you prove that, if you could solve the blank-tape halting problem, you could solve the ordinary halting problem.

The reduction works like this. Suppose there is an algorithm that decides whether a Turing machine that's given as its input halts when started with a blank tape. The input to this algorithm is a description of the Turing machine (its "source code", if you like) and it somehow analyzes its input and says either "Yes, that machine halts when started with a blank tape" or "No, it doesn't." We'll use this machine to determine if a given Turing machine $M$ halts when started with input $w$ (i.e., to solve the ordinary halting problem). The new algorithm is this: we take the description of $M$ and the string $w$ and we produce a new Turing machine description $N$. The source code for $N$ says, "First, delete your input. Then, write $w$ to the tape, one character at a time. Then, rewind the tape to the start and do exactly what $M$ does (i.e., it then includes a copy of $M$'s source code)." Note that each different value of $M$ and $w$ will give a different machine $N$. Now, we just ask our algorithm for the blank-tape halting problem if $N$ halts when given no input, and that tells us whether $M$ halts when given input $w$.

That is, we've used the blank-tape halting problem to solve the ordinary halting problem. However, we know that the ordinary halting problem is undecidable so something must have gone wrong. The translation of $M$ and $w$ to $N$ is completely fine: it's just some small edits to a machine's source code. So the impossible thing must have been the assumption that we have an algorithm for the blank-tape halting problem. There must be no such algorithm, which is the very definition of the problem being undecidable.