Thanks to Turing, we know that it is impossible to construct a machine that can prove for all machines whether they halt or not. This then has mayor implications on many other fields and theorems, since they can be restated using the halting problem.

However, what if we were to construct a machine that is able to realize that it is being 'fooled'? So rather than machine $H$ which returns halts if machine $M$ halts and diverges if $M$ does not, $H'$ returns halts if $M$ trivially halts (when $H$ returns halts), diverges if it trivially does not (when $H$ returns diverges), and paradox if the outcome depends on the outcome itself (when $H$ would be stuck in a paradox when being fed a program $M$ whose outcome depends on $H(M)$).

  • Would it be possible to 'side-step' the halting problem in this way? Or is there a way to show that even this extended machine $H'$ will struggle for certain machines $M$?
  • Would machines like $H'$ (and the formal system $F'$ that side-steps Gödel's incompleteness theorem in the same way) be useful in practice, or be crippled in some way?
  • 1
    $\begingroup$ The problem is that the machine has no idea if it is going to halt or not. That's what the Halting Problem asks...given a program, and a specified input, will the program halt or not? $\endgroup$ – lulu Jun 4 at 12:24
  • 1
    $\begingroup$ Would you consider a machine that always answers paradox to be correct? If not, please provide a rigorous definition of the inputs for which this answer is allowed. $\endgroup$ – Henning Makholm Jun 4 at 12:46
  • 2
    $\begingroup$ In particular, "depends on itself" is a very fluffy definition. Not that in the usual argument against the halting problem being decidable, the fact that the answer "depends on itself" is not an innate property of certain inputs to the halting problem, but a conclusion we reach from the assumption that the machine we're looking at correctly decides the halting problem. This assumption turns out to be counterfactual in all cases, so the argument does not actually identify any concrete input to the halting problem that would "depend on itself". $\endgroup$ – Henning Makholm Jun 4 at 12:56
  • $\begingroup$ @HenningMakholm I have clarified the question somewhat. $\endgroup$ – Qqwy Jun 4 at 12:59
  • $\begingroup$ "Stuck in a paradox" is not something that happens to the machine in the first place. The contradiction arises only in our reasoning, external to the machine about how we would expect it to answer. $\endgroup$ – Henning Makholm Jun 4 at 13:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.