>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.
Re:Show HN: XKCD-inspired StackSort
by fwenzel on Monday March 18, 2013 @05:20PM
(#5397194)
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.
>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.