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

That right there is what I'm asking about. I've never seen a definition that 
allows for a CA to have an infinite initialization other than to a default 
state.  Do you have a citation to a definition that describes this? I am 
having trouble coming up with a trivial way to define what would be the 
allowable initialization and what would be the disallowed initialization 
without making reference to something outside the realm of CAs. Perhaps if 
you can describe its state based on a RE function of its index or something?

Note that a TM that just gets its initial tape initialized to purely random 
symbols is also strictly more powerful than a TM that gets its tape 
initialized to a constant. The thing about the TM is you can show that if 
you initialize once cell per step, or if you keep a single extra register 
with the index of the highest-read cell, you can avoid doing an infinite 
initialization to start. (I.e., this would be the equivalent to the 
tack-initializers-on-the-ends you were talking about for the linear CA.)

> unless the CA runs infinitely without ever entering a 
> repeating sequence.

You mean, like a UTM might? ;-)

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

Post a reply to this message