clipka wrote:
> You just added an oracle.

Yep. That's kind of the point I'm making.

>> I'm not convinced. I'm not sure either way, mind. It just seems flakey
>> and not something you can assume.
> 
> Why not? Both CA and Turing machine are theoretical constructs anyway, 
> so you can assume just about anything.

Why not? Because if I allow for infinite initialization, I can calculate 
things with a CA that I can't calculate with a TM. You just pointed that out 
above.

> There - you just eliminated the need for any pre-calculation. As the 
> maximum propagation speed of any pattern in a CA is 1 cell per cycle, 
> you are guaranteed to have the "background pattern" wherever you need 
> it. Flaw fixed.

It's only "flaw fixed" if you want to claim that what you just created is 
rule 110. That's like arguing that a 1-state TM is universal, because all 
you have to do is add a few more states.

I'm not arguing that a CA can't be Turing complete. I'm arguing that 
*Wolfram's* CA requires an infinite amount of initialization *before* it can 
function as a UTM.

Given that a CA does an infinite amount of computation each step, I just 
don't know if that's problematic or not. Naturally Wolfram says it isn't, 
but I haven't heard it addressed anywhere, and I've looked.

-- 
Darren New, San Diego CA, USA (PST)
   Serving Suggestion:
     "Don't serve this any more. It's awful."

Post a reply to this message