Hacker News new | past | comments | ask | show | jobs | submit login

The halting problem doesn't matter if your API is required to define timeouts / time guarantees. Thus if a#1.0() returns "hello" after 100ms and a#1.1() returns "hello" after 20s, even though they return the same result, they are deemed functionally different. This follows real-world expectations where performance which suddenly slows to the point of unusability is considered breakage, even if the same result is returned in the end.



Replace it with any other nonsense.

In practice your time guarantee isn't going to let you produce a sound and complete static analysis that proves the equivalence of two arbitrary (modulo termination guarantees) functions.

In the real world all programs have a timeout set to the time to the heat death of the universe. This hasn't helped us make sound and complete static analysis.


I think that's essentially the same point as LBA in a sibling comment. The same intractability-in-practice applies to it: even if your timeout is 10 milliseconds, that's still (tens of) millions of operations on most modern CPUs and order of a gigabit written to/read from memory, which is a huge state space.


I think it's more like a lower bound on difficulty. In other words, halting is one of many guarantees that would need to be checked to ensure that an API didn't break, and it is impossible to check, so it cannot be done, irrelevant of the difficulty of the other problems (like timeouts or whatever).


I don't think you understood my comment - you don't need to check for halting if all methods in the API have timeout guarantees. Halting is only a problem if runtime is uncertain. If runtime is certain (again, because of promised performance figures) then it is entirely possible to verify whether an API has been broken or not.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: