Halting problem reduction to Halting for all inputs

Problem Detail: 

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?

Asked By : revisingcomplexity

Answered By : Rick Decker

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/41243