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

[Jesse J. <jes...@mi...>]

At 8:41 PM -0500 12/23/01, Patrick M Doane wrote:
>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.

I have a vague recollection of a more practical definition of a 
Turing complete language. It went something like: a language is 
Turing complete if it has sequential statements, some form of if 
statement, and I think one other thing that I can't recall.

>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.

Well, there's a lot of value in being able to generate the code from 
within C++. It's more portable and convenient than using something 
like Perl and it's better integrated with the other parts of the 
language.

   -- Jesse