“The other programmers keep accidentally writing code that ends up in an infinite loop. I'd like you to make a program that can reliably detect that.”

[–] elvith@feddit.de 32 points 2 years ago (9 children)

You may joke, but if I had a penny for every time someone asked me to solve a problem, that basically boils down to the halting problem, I'd be rich.

[–] randon31415@lemmy.world 7 points 2 years ago (5 children)

I have always wondered why the answer to the halting problem isn't: "If no output has been returned in X time, BREAK, restart program from beginning."

[–] Shalaska@programming.dev 13 points 2 years ago (2 children)

Because that will fail to detect a program that halts in X+1 time. The problem isn’t to detect if a program that halts halts, the problem is to generally create an algorithm that will guarantee that the analyzed program will always halt given an infinite time running on an infinite computer.

[–] randon31415@lemmy.world 6 points 2 years ago

Yes, that is the theoretical rational, but in use cases, if users always restart the program after X minutes, practical you can just hard reboot

[–] Brainsploosh@lemmy.world 2 points 2 years ago* (last edited 2 years ago)

But you could also do a mean time analysis on specific tasks and have it cut off at a standard deviation or two (90-98% of task times covered), and have a checkbox or something for when the user expects longer times.

You could probably even make this adaptive, with a cutoff at 2x the standard time, and updating the median estimate after each run.

load more comments (2 replies)

load more comments (5 replies)

load more comments (19 replies)