Aren't event loops infinite loops where memory might be unchanged for a long time?
MIT develops new tool that can interrupt infinite loops
11–20 of 72 posts
Re: MIT develops new tool that can interrupt infinite loops
#12Not even a single mention of the halting problem?
I was surprised too. I expected a mention of it, and a link to the poetic and intuitive proof-story of why its a problem would be good for the story too.
In case other HNers haven't read Scooping the Loop Snooper, I (re)submitted it:
Re: MIT develops new tool that can interrupt infinite loops
#13Not even a single mention of the halting problem?
Noob question time: what's the halting problem?
Re: MIT develops new tool that can interrupt infinite loops
#14Not even a single mention of the halting problem?
The halting problem doesn't apply.
Re: MIT develops new tool that can interrupt infinite loops
#15First of all the solution of this problem is computationally impossible so this tool makes me feel realy uneasy I'd never use it -- it would actually make predictable easily reproducible bugs impossible to report when this tool is activated. It makes an assumption that infinite loops are just stuck with a false condition and nothing else is affected by that, which I believe is fundametally false.
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
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.
Re: MIT develops new tool that can interrupt infinite loops
#16Not even a single mention of the halting problem?
Noob question time: what's the halting problem?
It's mathematically impossible to write a program that always correctly determines whether an arbitrary piece of code will halt (rather than get stuck in an infinite loop). Making that determination is referred to as halting problem.
Re: MIT develops new tool that can interrupt infinite loops
#17Not even a single mention of the halting problem?
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.
Re: MIT develops new tool that can interrupt infinite loops
#18Not even a single mention of the halting problem?
Noob question time: what's the halting problem?
The halting problem:
Given a program and an input, determine whether that program, given that input, will ever halt, or if it will loop infinitely.
One of the fundamentals of academic computer science is learning that it is mathematically impossible to solve the halting problem - which is why the grandparent comment simply notes "the halting problem" with no further explanation; it's a famous problem. (Don't feel bad, everyone has to learn something the first time!)
The poem linked elsewhere in this comment tree is a simple and pithy description of the mathematical proof.
For (many) more details, Wikipedia has plenty of information.
Re: MIT develops new tool that can interrupt infinite loops
#19Not even a single mention of the halting problem?
Does your computer have an infinite tape?
Re: MIT develops new tool that can interrupt infinite loops
#20Earlier 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…
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.