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.

Determining if a function throws is a pretty basic bit of information collected in bottom up codegen (or during pre pass of a whole program optimization) and in no sense NP hard. Compilers have been doing it for decades and it’s useful

Noexcept on the surface is useful, except for the terminate guarantee, which requires a ton of work to avoid metadata size growth and hurts inlining. If violations of noexcept were UB and it was a pure optimization hint the world would be much better

Interestingly, AUTOSAR C++14 Guidance (https://www.autosar.org/fileadmin/standards/R22-11/AP/AUTOSA...) had a "Rule A15-4-4 (required, implementation, automated) A declaration of non-throwing function shall contain noexcept specification." which was thankfully removed in MISRA C++2023 (the latest guidance for C++17, can't give a link, it's a paid document), - it mandates it only for a few special functions (destructors, move constructors/assignments and a few more).

Yes, true, thanks. I confused "will it throw given inputs&state?" with "can it potentially throw?".

I wonder, why compilers don't expose that information? Some operator returning tri-state "this code provably doesn't throw | could throw | can't see, break the compilation" could help writing generic code immensely. Instead we have to resolve to multi-storey noexcept() operator inside a noexcept qualifier which is very detrimental for the code readability...

You very likely can't always answer the question "will this function throw?", but it should be relatively easy to identify the subset of function that recursively call functions that are guaranteed not to throw. That's only a subset of all non-throwing functions of course.

Yes, my mistake was in confusion a run-time question "will it throw?" with "can it throw in theory?". The latter if I'm not mistaken again only requires a throw statement somewhere in a non-dead code, which is totally possible to find out for a code compiler could see.