18 Oct
2009
18 Oct
'09
5:45 p.m.
On 18 Oct 2009, at 18:14, Hartmut Kaiser wrote:
I agree with everything except Sebastians notion the preprocessor was not Turing complete, because it is (this has been shown in the past). But that's just a minor detail.
Are you sure? I'm sure it's not. Template instansiation certainly is, but I'm sure the preprocessor isn't, due to the lack of recursion or backtracking.
See here: http://tinyurl.com/yj6crup
While that is a very impressive piece of coding, it doesn't show NP- completeness of the preprocessor, as the code is hardwired to at most 2^30-1 reductions. Chis