MIT develops new tool that can interrupt infinite loops

However, the actual halting problem is moot in most of the references I see to it, as the halting problem is usually misused by the half-educated to make claims that 'nothing useful can ever be inferred about the behavior of any program, ever'.

For example, we built a tool to either estimate a reasonable ceiling on the stack usage (whole-program) or give up; it works very well and can detect when the structure of the program prevents this tool from operating correctly (nasty stack mischief or stack adjustments appearing in 'unusual' places). Quite useful for us, especially because we control the source code and know that we don't do naughty things to our own stack.

Entertainingly, on the way to build this tool, we encountered at a couple screeds about how this problem just plain can't be solved because it's equivalent to 'solving the halting problem'. Well, yes - in theory, but no - in practice.

As the economist famously joked in response to 'how are you'... "Compared to what?" The comparison here is to killing the program and losing all the data.

Obviously there are some big limitations on this - especially given that the state of the program isn't necessarily entirely defined in terms of the process itself, but also a series of possibly stateful network connections and os resources.

Another big limitation is that a straight-up infinite loop at the level of the binary isn't necessarily the only way that a program could get stuck - we could be going around quite a complex loop at the binary level in response to an _interpreted_ loop, and killing the whole interpreter isn't necessarily going to return the program into a usable state.

That being said, what else are you going to do in this case? A number of the alternate solutions here seem to involve time travel.

Some fun possibilities - if you can replicate the OS state, and there's no important network state held open by the program, you can make a bunch of copies of the broken program and try lots of different approaches. You might also be able to fire up the program cleanly, get to the main event loop, identify what that looks like, and just magically splice that state back on top of the broken program in the hope that whatever is happening in global data structures is self-contained enough to recover from.

I understand that there are many reasons why this probably won't work... that being said, the baseline here is zero (especially if the users are made very aware that this program isn't a safety net of any kind and don't become more careless thinking that there's a magic 'fixit' program out there).

We have a 'little bit' of recursion where we know that we won't go around the recursion more than once and we've hand-hacked that it. We have similar hacks to deal with indirect calls.

I'm not saying we've solved the problem for arbitrary code; I'm saying that solutions that fall very far short of solving problems for arbitrary codes are still enormously useful. Many compiler optimizations don't work for 'arbitrary code' either, for example, and know just enough to bail out when they see an irreducible flowgraph or a bizarre indirect jump, etc.