Darren New wrote:
> Kevin Wampler wrote:
>> Are you *sure* that rule 30 is the right CA here?  
> 
> No, actually. I thought that sounded wrong, and 110 sounds much more 
> like what I remember, but I wasn't about to dig out the 30 pound tome to 
> check. :-)

I see.  I had asked partially since if rule 30 isn't Turing complete it 
provides a nice counterexample to the "it's a CA with non-trivial 
behavior so it's probably Turing complete" viewpoint (which you were 
also arguing against).


>> and there was a later proof by Matthew Cook establishing this provided 
>> proper tape initialization and processing is done.
> 
> Right. There's a proper proof *providing* the initialization of the 
> first state is done. That's what I'm not sure is valid. I'm not saying 
> it isn't, but I'm not convinced it is. AFAIR, the definition of a turing 
> machine requires anything past a finite initial portion of the tape to 
> be all initialized to the same symbol.

I swear I'd read a nice blog post about this at some point but I cannot 
seem to find it again.  As far as I remember the main gist was "you have 
to be careful with the initialization since it's possible to combine two 
non-Turing complete components and get a Turing complete result"

Ahh, I *think* this is what I was remembering:

http://forum.wolframscience.com/showthread.php?s=&threadid=1472

As near as I can tell, maybe it's best to view rule 110 as "weakly 
universal" since the universality proof requires an infinite (and AFAIK 
non-repetitive) initialization?  That seems to convey the idea that it 
has some interesting properties with respect to Turing completeness, but 
that it's not quite the full-blown form of Turing completeness you'd 
normally expect.

Post a reply to this message