Comment by _delirium | Hacker News Reader

Comment by _delirium | Hacker News Reader

Parent Full thread

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 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.

> 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.

Good 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.

The 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.

Only 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.

Reply on news.ycombinator.com