Re:Show HN: XKCD-inspired StackSort
by asveikau on Monday March 18, 2013 @03:12PM
(#5396455)
Can you also write code to detect whether a program will run forever for a given input? ducks
[ Parent
| on HN ]
I looked for a way, but turns out it's not possible with JS. Browsers will stop infinite loops after a few seconds, though.
EDIT: Ah, I missed the joke.. what I meant was that I looked for a way to stop the JS if it ran for more then a second.
I believe this is the joke: http://en.wikipedia.org/wiki/Halting_problem
>In computability theory, the halting problem ... is equivalent to the problem of deciding, given a program and an input, whether the program will eventually halt when run with that input, or will run forever. Alan Turing proved in 1936 that a general algorithm to solve the halting problem for all possible program-input pairs cannot exist.
Sure. gkoberger transformed that statement into "can you detect if it has been running for an unreasonable amount of time". Not possible in advance, but certainly detectable in hindsight. Just, perhaps, not in JS.
> turns out it's not possible with JS.
No kidding... :-)
rm999 is correct; it was a joke about the halting problem. (The best kind of joke, obviously.) The broader point I was trying to make with the joke, though, is it's very hard to write code that will predict what another piece of code will do.
Pray, gkoberger, if you put into the machine wrong figures, will the right answers come out?