I was recently tasked with the traveling salesman problem on a project. My first pass was quick but produced sloppy inefficient results. Well boss didn’t like it so he had me go back at it again so it would be far more accurate. Well now it slogs through figuring out an optimal solution of several thousand points.
Comment on They Need To Stop Doing This
elvith@feddit.de 8 months agoYou 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.
drcobaltjedi@programming.dev 8 months ago
randon31415@lemmy.world 8 months ago
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.”
niartenyaw@midwest.social 8 months ago
what if it needed just one more second to complete?
WhiskyTangoFoxtrot@lemmy.world 8 months ago
Damn Vogons.
Shalaska@programming.dev 8 months ago
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.
Brainsploosh@lemmy.world 8 months ago
But you could also do a mean time analysis on specific tasks and have it cut off at a standard deviation (90% 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.
xigoi@lemmy.sdf.org 8 months ago
Yeah, accidentally running into the halting problem is common in automatic code analysis.
PoolloverNathan@programming.dev 8 months ago
It’d be nice if we wrote something to detect it running into the halting problem.