Orchid XP v8 wrote:
> 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?

Because the CAs that are turing complete prove they are so by having 
building blocks for (for example) XOR and NOT gates, which we already know 
are turing complete. In addition, the CAs that are known to be turing 
complete don't require an infinite grid to run in but only an unbounded one.

Wolfram's CA requires an initialization of an infinite amount of data before 
you start the CA in order for it to emulate a turing machine, as well as 
doing an infinite amount of processing each step during the emulation.

Now, granted, a CA theoretically operates on an infinite amount of data each 
step. I'd agree the rule is turing complete if (a) someone much smarter than 
I agreed that an infinite amount of initialization is acceptable or (b) that 
the rule did its own infinite initialization before it started computation.

>>> 2. Nobody has disproved it.
>>
>> That's not how math works.  "Hey, P=NP!   Well, nobody disproved it."
> 
> Nobody has proved it either.

Right. And as far as I'm concerned, nobody proved Rule 30 is turing complete 
either.

I mean, it's fine to say "I think it is possible to prove it even tho we 
didn't yet", or "I think your objection based on infinite amounts of 
initialization is not valid", or "I just have this gut feeling that it's 
correct."  But "because nobody has disproved it" doesn't add to any of 
these. :-)

> A question which has a proof one way, and would require only a single 
> counter-example to disprove the other way, I think can be considered 
> proven.

Uh, no, there is no proof. There's a flawed proof. But (AFAIK) what he 
proved the CA does isn't equivalent to a Turing machine.  A proof that's 
wrong, or that proves something other than what the author intended, isn't 
"proof without a disproof". It's nothing.

Maybe I'm mistaken, and an infinite amount of initialization isn't 
problematic to the proof. If so, some sort of citation to why would be handy.

-- 
Darren New, San Diego CA, USA (PST)
   Forget "focus follows mouse." When do
   I get "focus follows gaze"?

Post a reply to this message