Or worse than NP-hard: C++ template instantiation and the C preprocessor are Turing complete. (Except that I believe C++ requires some fixed limit on the maximum instantiation depth, but even so it's still exponential complexity.)
I believe you can encode paradoxes in C++ templating.
Something about two specializations which are mutually impossible because they reference eachother. So you can say:
A is of type T <=> B is not of type T
B is of type T <=> A is not of type T
Where <=> is if and only if.
In which case it is paradoxical to say that A is of type T. But also paradoxical to say that A is not of type T.
Note that "a template for which no valid instantiation is possible" is actually ill-formed, no diagnostic required.
That said, it's not clear to me what part of "you can write uninstantiable templates" is surprising, so I'm probably not understanding correctly. Maybe you could find the C++ code you're talking about? I would be interested.
That's surprising, the C preprocessor is pretty crippled. It's creator intentionally made it so people won't abuse it to create full blown mini languages.
Did you get things mixed up or is there actually a way the c preprocessor can be turing-complete ?
Not sure whether this proves turing completeness of the preprocessor or not(probably not) but Simon Tatham has a great(and somewhat disturbing) write-up[1] on creating arbitrary control structures using macros in C. He even goes as far as providing a library of helper macros for doing things like making gensyms, etc.
If nothing else, it does demonstrate that you can do a lot more in the preprocessor than you might think, and this is at least a significant subset of what true MP macros are used for in Lisp most of the time. Except much gnarlier...
I believe that while you can't encode an infinite tape, you can very easily define an arbitrarily large tape, so, while not technically Turing complete, it is close enough.
