Orchid XP v8 wrote:
>>> 1. It seems a logical and intuitive result.
>>
>> Uh, no?
> 
> Intuitive is in the eye of the beholder, is it not? Besides, you just 
> said yourself that there are CAs which are known to be Turing-complete; 
> why not this particular one?

Are you *sure* that rule 30 is the right CA here?  As far as I'm aware 
of could find via Google rule 30 is *not* believed to be Turing 
complete.  It's entirely possible that I missed something, but it's a 
class III automaton rather than a class IV CA so there's a reason I'm 
doubting this.

It seems more likely that the proof you're talking about was done for 
rule 110, which is the CA that Wolfram proposes to be Turing complete, 
and there was a later proof by Matthew Cook establishing this provided 
proper tape initialization and processing is done.

If you do have a reference giving the proof for rule 30 I'd be 
interested to see it since it doesn't strike me as an intuitive result 
and thus I'd probably be able to learn something from it.

Post a reply to this message