31–40 of 72 posts
It seems like it'd be a huge mess to try to write code succeeding the loop which tries to handle the case where your loop code didn't complete like you expected it to.
Earlier quoted context omitted.
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 fini…
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…
> 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.
Very little code is written that way, but when code is written that way, it allows much more interesting things to happen in software and hardware both.
Aren't event loops infinite loops where memory might be unchanged for a long time?
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
$ gdb /Applications/Safari.app/Contents/MacOS/Safari $PID
Earlier quoted context omitted.
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 fini…
def is_collatz(n):
s = set()
while n not in (1, 2, 4):
if n % 2:
n = 3 * n + 1
else:
n /= 2
if n in s: # Non-Collatz loop
return False
s.add(n)
return True
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.
What few people realize, is that most completely arbitrary programs are very uninteresting. More interesting programs have characteristics that would very often allow to statically prove that all of their loops that should terminate indeed will terminate. And even interesting loops for which it would not be in the first time possible to determine that often gain in clarity from being slightly changed so that the tool can do its work.
IIRC MS has a tool that does sort of that for windows drivers.