Re: [GD-General] Re: C++ turing complete

[Patrick M D. <pa...@wa...>]

This is getting off-topic, but this discussion has not been focused
entirely on gaming, so...

On Sun, 23 Dec 2001, Jesse Jones wrote:

> My recollection of Turing machines is a bit rusty, but you can use
> template meta-programming just like you would use a functional
> language and you can also write stuff like compile time if statements
> and loops. Sounds Turing complete to me...

This kind of meta-programming is certainly possible to do as long as
progress is being made (at least in my experience with templates).  For
example, one can compute factorial numbers using templates because this
process terminates.

This might be picking on a fine point, but a programming language is
Turing-complete if it can simulate the behavior of a turing machine with
finite storage capacity.  One of the fundamental properties of such
machines is that the halting problem is undecidable.  In fact, Turing
machines were originally formalized to prove this.  So the idea of being
Turing-complete while ensuring that computation terminates doesn't seem
very compatible.

Regardless, templates provide an expressive meta-language for static
compilation.  I'll admit that I don't fully understand the excitement as
one can do this in a more powerful (and understandable) fashion by simply
generating C++ code.

Patrick