[tsimionescu]

I think their point was that the halting problem is NP hard, it is in fact undecidable. Since there is no algorithm that can solve it, there is no point in talking about complexity of that algorithm.

Alternatively, Java shows that it is very much possible to do this - the compiler can enforce that a function can't throw exceptions (limited to checked exceptions in Java, but that is besides the point). The way to do it is easy: just check that it doesn't call throw directly, and that all of the functions it calls are also marked noexcept. No need to explore things any deeper than that.

Of course, the designers of C++ didn't want to impose this restriction for various reasons.