Escaping Infinite Loops 204
twocentplain writes in with an MIT news release about Jolt, a research project designed to unfreeze software stuck in an infinite loop (for a subset of infinite loops). It uses a combination of static instrumentation (using LLVM) and a run time watchdog that checks the program state during loop iteration; when a duplicate state is detected it permits the user to take one a few actions to escape the loop. The authors claim it works well enough that the program can often continue operating properly. The original paper contains detailed case studies.
Re:Halting Problem (Score:5, Interesting)
Here, the Halting Problem doesn't really apply, because if all else fails, you can (in theory) take every combination of programs up to N bits in length, and every combination of inputs up to M bits in length, and make a table of size 2^(N + M) saying whether a given program halts on a given input by running it and looking for a duplicate state. Of course that's impossible in the real world, but it does demonstrate that there's nothing about this research that's violating established principles of computer science.
And in a sense, that seems to be what they're doing here: checking "has this program existed in this exact same state before?", because if it has, you're in an infinite loop. I seriously doubt it's as effective in the real world as they claim though: in my experience infinite loops simply don't happen in computing anymore. If your computer locks up, it's probably because you're in deadlock, or waiting on the disk or the network.
Illiac had infinite loop detection (Score:5, Interesting)
Here at the U of I, we built the 4th computer ever made: the Illiac [wikipedia.org]
24 hours a day, an operator would sit at the computer to operate it. "Software" or jobs would be submitted by faculty. When one finished, the operator would load the next one.
Since only one job could be running at a time, it was quite important to detect infinite loops. The last bit of the ALU was connected to a speaker, and would produce sound similar to static when the computer was running correctly. If an infinite loop was encountered, then the static would suddenly hum a pitch, and the operator would kick out the job, and move to the next.
As the story goes, the very first machine music was written by a math professor, and submitted as an Illiac job, as a prank on the operator. Sometime around 3am, the operator picked up the next job and fed it to the machine. Immediately, the Illiac began playing "Hail to the Orange"!