Want to read Slashdot from your mobile device? Point it at m.slashdot.org and keep reading!


Forgot your password?

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.
This discussion has been archived. No new comments can be posted.

Escaping Infinite Loops

Comments Filter:
  • Re:Halting Problem (Score:5, Interesting)

    by AdmiralXyz ( 1378985 ) on Tuesday August 02, 2011 @05:32PM (#36965282)
    Joking aside, this really has nothing to do with the Halting Problem, because the Halting Problem is a statement about Turing machines, which have unbounded space. Actual computers are not Turing machines: because they have finite memory, they have a finite (though very large) number of states, and are actually finite-state automata.

    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.
  • by uigrad_2000 ( 398500 ) on Tuesday August 02, 2011 @05:59PM (#36965608) Homepage Journal

    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"!

"Well, it don't make the sun shine, but at least it don't deepen the shit." -- Straiter Empy, in _Riddley_Walker_ by Russell Hoban