[kazagistar]

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).

[solatic]

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.