Saturday, April 15, 2006

C++ Templates Turing Complete???!!!

Incredible!!! I did not believe it until I ran the program myself. I found that C++ templates are Turing Complete here. Reading the post, I immediately copied the code to my editor and tried to compile. I saw the CPU and memory usage going higher by time almost at an exponential rate. What a practical proof!!! Here is a paper which proves it theoretically. Here is the interesting piece of code, give it a try!

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) { }

No comments: