3 ms·
In theory I believe it can actually detect all infinite loops, for an extremely generous definition of "can detect". On a finite-memory machine, a computation f
by _delirium 15y ago
In theory I believe it can actually detect all infinite loops, for an extremely generous definition of "can detect". On a finite-memory machine, a computation fails to halt iff it eventually repeats a state, which it must do in finite time, since there are only finitely many possible states (the finite-ness is what makes the halting problem not apply). However, that finite time might be extremely large, perhaps longer than the age of the universe. A http://en.wikipedia.org/wiki/Busy_beaver http://en.wikipedia.org/wiki/Busy_beaver function gives an upper bound on how long it can be.
But yeah, the practical use is to tell you when a computation is already looping, for the large subset of infinite loops that result in states being repeated relatively quickly.
- Mgccl 15y agoThe busy beaver function gives very loose upper bound... A better bound: If the computer can be described with $n$ bit of information, and a program did not terminate with $2^n+1$ operations, then the program has a infinite loop. $n$ is usually the memory + cpu cache size.
- derobert 15y agoOnly if you take a very liberal definition of memory. The following probably isn't an infinite loop, even though it'd look like one under normal definitions of memory (either RAM or RAM+disk): $ while ping -W 2 -q -c 1 www.google.com; do sleep 10; done Eventually, the network will go down.
- rcfox 15y ago> On a finite-memory machine, a computation fails to halt iff it eventually repeats a state This is too strong of a statement. Lots of software simply loops, repeating the same state over and over, until an external interrupt occurs.
- _delirium 15y agoGood point; I guess I was thinking of the simplified textbook case of computations with no external interaction. I wonder if this MIT system is able to exclude the most likely false positives, like polling for input? On the other hand, maybe polling too long for input counts as an infinite---or at least, too long---loop for their use-case of interrupting user programs that seem to be hanging, so that the user can save.