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?


1 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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