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?