0

The simplified explanation to the Halting Problem relies on the contradiction in if you have a Turing Machine H that can decided if a program p halts, it loops forever if p halts and halts if the p doesn't. Then be feeding this program into it's self you end up with the logical contradiction.

I feel like I am missing something fundamental here. Why do the outputs of H have to be loop or halt, rather than 0 or 1? Since we start from the assumption that H is some magic box which can decided the Halting Problem, why can'y we assume that it gives a yes/no answer and then always halts?

MikeS159
  • 123
  • 4
  • Perhaps this has been already been clarified by the answer, but note that the output isn’t “loop” or “halt”, the behavior is that the the program loops or it halts. In other words, depending on what the program gets back from the halting black box, it runs either the code “while True, continue,” or “return.” – spaceisdarkgreen Sep 26 '18 at 14:04

1 Answers1

4

Yes, we can assume there is a "universal halting predictor" $H$ that produces output $0$ if Turing machine $P$ with input $I$ never halts and $1$ if its does halt - and we assume $H$ always outputs either $0$ or $1$ and is always correct.

But the point of the proof is that we could then construct a Turing machine $H'$ which, when given input $I$, feeds its own description together with input $I$ to $H$. $H'$ then does the opposite of whatever $H$ predicts it will do. This means that $H$ cannot predict what $H'$ will do with input $I$, so $H$ is not after all a universal halting predictor for Turing machines.

Note that this argument does not rule out a "magic" (i.e. non-algorithmic) halting predictor $M$ for Turing machines. It would not be possible to construct a contradictory $M'$ around $M$ because the non-algorithmic $M$ is part of $M'$, so $M'$ does not have an algorithmic description which it could feed to $M$. In other words, magic $M$ may be able to predict whether any Turing machine will halt, but $M$ and $M'$ are not Turing machines.

gandalf61
  • 15,326