Is C++ as a formal language recursively enumerable? If yes, is there any invalid C++ code that takes "infinite" time to compile?

  • 2
    $\begingroup$ In fact, C++ template language is Turing complete. Why "invalid" C++? Even valid C++ can take an infinite time to compile (in theory). $\endgroup$ May 4 '14 at 11:36
  • $\begingroup$ Enumerability and compilation time are not as closely related as you might think: compilation involves more than parsing. $\endgroup$
    – Raphael
    May 4 '14 at 11:46

In theory this code should compile infinitely

template<long long K>
struct t {
  enum { value = (K&1) ? t<K+1>::value : t<K-1>::value};
int main() {
  int i = t<1>::value;

But in real life compilers are limiting template instantiation depth. Another thing is that long long is limited so you cannot represent all integers.

  • $\begingroup$ I was under the impression that the standards specify minimums on such (just like length of names), so a compiler that supports greater than minimum depth might almost be considered to be extending the language as a programmer can only rely on the minimum depth being implemented without implementation-specific knowledge. (Even that is theory since a compiler might falsely claim compliance with a standard.) $\endgroup$ May 5 '14 at 15:34
  • $\begingroup$ Note: instead of using long long you could encode Peano Numbers in the type system. $\endgroup$ Oct 22 '15 at 17:38
  • $\begingroup$ @PaulA.Clayton: The C++ Standard specifies recommended minima and the C++ compilers usually provide flags to adjust the default limits they implement. $\endgroup$ Oct 22 '15 at 17:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.