News for hackers. Stuff that matters.
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
Re:Show HN: XKCD-inspired StackSort by gkoberger on Monday March 18, 2013 @03:41PM (#5396641)
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.

Re:Show HN: XKCD-inspired StackSort by rm999 on Monday March 18, 2013 @03:45PM (#5396665)
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.

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.
Re:Show HN: XKCD-inspired StackSort by asveikau on Monday March 18, 2013 @03:52PM (#5396701)
> 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.

Re:Show HN: XKCD-inspired StackSort by rozap on Monday March 18, 2013 @03:53PM (#5396718)
Pray, gkoberger, if you put into the machine wrong figures, will the right answers come out?
Re:Show HN: XKCD-inspired StackSort by nixhope on Monday March 18, 2013 @11:17PM (#5398694)
if (eval(code_sample)) {return true;} else { return false;}

// Running time: O(1), for values of 1 approaching infinity