C++ templates are turing complete

Here you will find a short C++ program that takes more than 24 hrs to compile on a dedicated dual processor, 1GB memory machine!! Here we go...

template<int Depth, int A, typename B>
struct K17 {
static const int x =
K17 <Depth+1, 0, K17<Depth,A,B> >::x
+ K17 <Depth+1, 1, K17<Depth,A,B> >::x
+ K17 <Depth+1, 2, K17<Depth,A,B> >::x
+ K17 <Depth+1, 3, K17<Depth,A,B> >::x
+ K17 <Depth+1, 4, K17<Depth,A,B> >::x;
};
template <int A, typename B>
struct K17 <16,A,B> { static const int x = 1;
};
static const int z = K17 <0,0,int>::x;
int main(void) { }

Source: C++ Templates are Turing Complete by Todd L. Veldhuizen

This program is taken from the above paper which takes unreasonably long to compile. I belive, a simple dynamic programming solution will reduce the exponential time required by this program to compile to polynomial time. I also believe, it might be quite difficult to apply dynamic programming solution, in general, to all C++ programs of this nature. You need to have a good understanding of template meta-programming to make sense of this program. One good article by the same author is here:

This post is motivated by a anonymous comment I received on an earlier post. I am quoting him here:

"It is ___provably___ impossible to write a correct C++ parser which will complete compilation with either success or failure because the C++ template system is Turing complete. This means that code generation is based on a turing complete program. Code generation in C++ isn't based on a program description, but an actual turing complete program. As such, it is subject to the halting problem. Therefore, it is unknowable whether a compilation will complete, and unknowable if you are looking at a valid C++ program."