clipka wrote:
> "An initial state (time t=0) is selected by assigning a state for each 
> cell."
> 
> (Wikipedia)
> 
> Isn't that plain enough? You assign a state for /each/ cell. CA's don't 
> seem to make any limitations on this.

Well, from that same page:

"""
It is usually assumed that every cell in the universe starts in the same 
state, except for a finite number of cells in other states, often called a 
configuration. More generally, it is sometimes assumed that the universe 
starts out covered with a periodic pattern, and only a finite number of 
cells violate that pattern. The latter assumption is common in 
one-dimensional cellular automata.
"""

So you "generally" don't start with an infinite aperiodic pattern.

What I was really interested in was a proof that starting with a periodic 
pattern (except a finite number of cells) didn't give more computing power 
to the CA than starting with a single state (except a finite number of 
cells). Because Wolfram is arguing about the computational power of Rule 110.

> Just name /any/ rule for that pattern 

I don't think that works, because then it lets the CA calculate stuff a TM 
cannot, and I think that would lead to a trivial disproof of the 
Church-Turing thesis.

Now, a pattern that differs from a regular repeating pattern in only a 
finite number of places? Sure, that's likely good.

But if Wikipedia says a repeating pattern for linear CAs is common, I'll 
assume that's sufficient to quell my disquiet with the Rule 110 proof in 
that regard. I'd still like to see a proof that having the repeating pattern 
doesn't add computational power, which is what the Crawley paper was 
apparently discussing. I'll have to take time to look at that closer.

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

Post a reply to this message