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

[Jamie F. <ja...@qu...>]

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

One thing that may be useful, that I studied at uni: a URM (unlimited
register machine) is equivalent to a Turing machine. It has 4 instructions:

1. Zero a register
2. Increment a register by 1
3. Set a register to the value of another register
4. If two registers are equal, jump to a program line

This is provably equivalent to a UTM, and tends to be somewhat easier for us
programmer types to understand and use.

So if you can do these things, the language is complete.

Jamie


-----Original Message-----
From: gam...@li...
[mailto:gam...@li...]On Behalf Of
Jesse Jones
Sent: 24 December 2001 03:49
To: Patrick M Doane
Cc: gam...@li...
Subject: Re: [GD-General] Re: C++ turing complete


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

_______________________________________________
Gamedevlists-general mailing list
Gam...@li...
https://lists.sourceforge.net/lists/listinfo/gamedevlists-general