Am 04.01.2011 21:56, schrieb Darren New:

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

No, not really. Your argument why 110 is flawed is based on the 
assumption that its initialization /may/ be some kind of oracle. My 
argument shows that this is not necessarily the case - and in particular 
that it is /never/ the case if the CA is pre-initialized with a regular 
pattern, as in that case you can always build a CA that simulates the 
original CA without requiring infinite initialization; as the proof for 
the Turing-completeness of Rule 110 uses such a regular pattern, there 
is no oracle involved in the setup.

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

And that's no problem, because CA are allowed to have that /by definition/.

Yes, that might make a CA /more/ powerful than a UTM. But that doesn't 
mean it can't /simulate/ a UTM (thus making it Turing-complete), or that 
its setup procedure /necessarily/ makes it any more difficult than a UTM 
to actually simulate it in real life, or whatever problem it is you have 
with that infinite initialization. In some cases it might be, but in the 
case of simulating a UTM it isn't.

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

Note that even if you kind of have infinite "ROM" in a CA, within 
limited time you can only access a limited amount of it (at most 2*N+1 
cells in a 1D automaton, where N is the number of steps you compute), 
because the information needs to propagate to the place where the output 
is to end up. So effectively you're only initializing a limited number 
of cells, unless the CA runs infinitely without ever entering a 
repeating sequence.

Post a reply to this message