You cannot generally decide the problem, because at best your algorithm can only practically determine "the Turing Machine under test has not returned...yet. The Turing Machine capable of ultimately deciding the returnability of TMuT, would necessarilly have practically infinite runtime.
And for that matter, bring yourself out of TM's and you've got all sorts of other nasty constraints that make the Halting Problem Solver unimplementable in the real. What happens when brownouts happen? Single-event-upsets? Rowhammer events? You couldn't win in the purely abstract theoretical, so even trying to get a literal win in the real doesn't stand a chance.
Halting Problem is Computer Science's realization that there is always a bigger Turing Machine, much like how mathematicians understand there to be infinitely many primes. Within the constraints of the axiomatic model of computation; you cannot put a pin in the entire space. Only increasingly large swathes of the space at the cost of completely unreasonable respurce expenditure.
Or as I like to think of it, HP is the understanding that only 2 people ever understood this code in it's totality. God, and me when I was writing it. And I long ago ditched that original context that allowed me to claim I understood it.
No comments yet.