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)rightarrowlangle,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
