# Is there C++ code that takes infinite time to compile?

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

• In fact, C++ template language is Turing complete. Why "invalid" C++? Even valid C++ can take an infinite time to compile (in theory). May 4 '14 at 11:36
• Enumerability and compilation time are not as closely related as you might think: compilation involves more than parsing.
– 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.

• 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.) May 5 '14 at 15:34
• Note: instead of using long long you could encode Peano Numbers in the type system. Oct 22 '15 at 17:38
• @PaulA.Clayton: The C++ Standard specifies recommended minima and the C++ compilers usually provide flags to adjust the default limits they implement. Oct 22 '15 at 17:39