Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

MIT develops new tool that can interrupt infinite loops

bostinnovation.com

Post reply on HN
Print view View original

21–30 of 72 posts

Re: MIT develops new tool that can interrupt infinite loops

#21

Post by jesboat »

prolepunk wrote: post #15
adrianN wrote: post #7

Earlier quoted context omitted.

It appears to take memory snapshots. If it detects a repeat in the snapshots it knows that the program will loop indefinitely. Of course it can't detect all infinite loops, but a sizeable subset.

It only takes memory snapshots to find next end-of-loop instruction in binary code to jump to it, with source equivalent of it being: while True: if loop_var > 9000: break loop_var += 1 My main complaint that might as well detect a repeat in snapshot but I really doubt that it detects extraneous changes in loop variables that might be caused by stray infinite loop logic. From programming perspective it's better to cr…

From programming perspective it's better to crash hard and let the error be known rather than fail silently and introduce more sublte errors.

From user perspective, what is the point of saving file in a program that is falling over when you could potentially save a corrupt file and instead of retaining some of the work the user will end up with a blob of useless data. I guess you could do Save As... and then manually compare changed data with last save. Still I'd be extremelly suspicious of it.

I am absolutely shocked that nobody else has even hinted at this. I wouldn't recommend this tool in almost any circumstance.

Re: MIT develops new tool that can interrupt infinite loops

#22

Post by xyzzyz »

DasIch wrote: post #17
achompas wrote: post #13

Earlier quoted context omitted.

Noob question time: what's the halting problem?

Basically the halting problem states that it is impossible to determine whether or not a given program halts under the assumption that it is executed in a turing complete machine. Due to the fact that a program is a composition of programs which at the lowest level are loops and instructions this also means that it is impossible to determine whether or not a loop halts.

Due to the fact that a program is a composition of programs which at the lowest level are loops and instructions this also means that it is impossible to determine whether or not a loop halts.

It is easily provable that this is theoretically possible, but the required time is too long for it to be applicable. Suppose your memory has N states. Run your program through N+1 computation steps and if it's not already finished, then it will never halt.

Thing is, N is very large for real memory, so this straightforward approach is not applicable. However, there's much room to improve this algorithm and I assume that's what the MIT folks did.

True halting problem is about computational devices with infinite memory.

Re: MIT develops new tool that can interrupt infinite loops

#23

Post by derobert »

Mgccl wrote: post #20
_delirium wrote: post #10

Earlier quoted context omitted.

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 longe…

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.

Re: MIT develops new tool that can interrupt infinite loops

#24

Post by rcfox »

_delirium wrote: post #10
adrianN wrote: post #7

Earlier quoted context omitted.

It appears to take memory snapshots. If it detects a repeat in the snapshots it knows that the program will loop indefinitely. Of course it can't detect all infinite loops, but a sizeable subset.

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 longe…

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

Re: MIT develops new tool that can interrupt infinite loops

#25

Post by edge17 »

matthavener wrote: post #9

I've done this with MS Word and the VS debugger. Word crashed while I was editing a huge document. I simply skipped a few instructions down, returned to Word, saved the document, and restarted Word. When your options are either 1) crash, or 2) possibly recover to some working state, it's pretty easy to choose option 2.

i wish i could do that for safari
Post reply on HN