Halting problem reduction to Halting for all inputs

Question

I was going through my book of revision and I would like someone hints on this.

• The Halt for All Input problem (HAI) takes a machine and tell if this machine halts or not for any input
• We prove it is unsolvable by proving it reduces to the halting problem

The book says:

• Build a $M'$ that does the follwoing
• $M'$ erases its input (?)
• $M'$ writes I on its tape (did we not just erased this?)
• $M'$ simulates $M$

Can someone explain this reduction?

Answer 1

There are a couple of points here. First, you're confusing the direction of the reduction: You're reducing HALT to HAI, not the other direction. Then, your book suggests the transformation $(\langle\,M\,\rangle, x)\rightarrow\langle\,M'\,\rangle$ where $\langle\,M\,\rangle$ is the description of a TM $M$, $x$ is a string, and $\langle\,M'\,\rangle$ is the description of a TM:

M'(y) =
   erase the input y
   write x on the tape  // second point: we're erasing and writing different strings
   simulate M on x

Now if $M$ halts on input $x$, then $M'$ will halt on every input $y$ and so will be an instance of HAI. Conversely, if $M$ fails to halt on $x$, then $M'$ will not halt on any input $y$ and so will not be in HAI.

From here, we can see that HAI is undecidable. If it were, then we could decide whether $M'$ would halt or not, and hence we'd be able to decide whether $M$ halted on $x$. In other words, we'd have a decider for HALT, which we know is impossible.