News for hackers. Stuff that matters.

A comment on Eliud Kipchoge Breaks Two-Hour Marathon Barrier. Parent comment

Re:Eliud Kipchoge Breaks Two-Hour Marathon Barrier by not_kurt_godel on Saturday October 12, 2019 @04:02PM (#21235811)
> It's a slow and costly process, but it gets the job done and it made me wonder if there are algorithms like that, that can compute results otherwise uncomputable

The catch with certain classes (maybe/probably all? disclaimer: am not theoretical computer scientist/mathematician) of uncomputable problems is that they are such that there is no notion of "getting closer" to the solution that's analogous to traversing the desert to a known location. There is no way to verify whether the next incremental step is taking you closer to or farther from the solution because calculating such is essentially the same problem as the root problem. See https://en.wikipedia.org/wiki/Undecidable_problem

[ Parent | on HN ]
Re:Eliud Kipchoge Breaks Two-Hour Marathon Barrier by YeGoblynQueenne on Monday October 14, 2019 @04:17AM (#21246125)
No, you're right. I say "uncomputable" but that's not what's happening here. The problem is not "uncomputable" it's just that the result is negative (X men can't cross Y distance carrying Z provisions).

Thanks for pointing this out, my bad for using "uncomputable" wrong.

[ Parent | on HN ]