🚀 go-pugleaf

In article <92357.182747RSMA410@HAIFAUVM.BITNET>, Dan Gordon <RSMA410@HAIFAUVM.BITNET> writes:
> In article <1992Dec15.162545.25338@news.unige.ch>, swann@divsun.unige.ch (SWANN
> Philip) says:
> >
> >In Casti's book "Alternative Realities" there's a conjecture
> >that Wolfram's classification of Cellular Automata into classes
> >can be mapped into Chomsky's Hierarchy of Formal Languages. He
> >cites Wolfram on this. Is there any recent work on the subject?
> 
> Cellular automata, in the unrestricted sense, have long ago been
> proved to be computation universal, i.e., they can simulate any
> Turing machine - see A.R. Smith III, "Simple computation-universal
> cellular spaces, JACM 18(1971), 339-353.  This means, of course,
> that they can also simulate any of the following: finite automata,
> pushdown automata, and linear-bounded automata.  So cellular
> automata can be "mapped" to the Chomsky hierarchy (if this is the
> intended meaning of "mapping into the Chomsky hierarchy").
> 
> Wolfram, in "Statistical mechanics of cellular automata," Rev.
> Modern Physics 55(1983),601-644, studies so-called _totalistic_
> cellular automata.  In these automata, each state is considered
> as a non-negative integer, and the state transition function
> depends only on the sum of the states of a cell's neighborhood
> (the sum includes the cell's own state).  Wolfram conjectured
> that these automata are also computation-universal.
> 
> This conjecture about totalistic cellular automata was proved
> true in: D. Gordon, "On the computational power of totalistic
> cellular automata," Math. Systems Theory 20(1987), 43-52.
> It is shown there that totalistic cellular automata can simulate
> an arbitrary Turing machine in linear time - actually, twice
> real time.  Needless to say, I was somewhat surprised to learn
> from the above posting that this problem is still regarded by
> some as a conjecture.

Sorry, my question was vague. I've now found the original
reference.... The classification is of the limiting behavior of
*one-dimensional* automata as:

A. The initial pattern disappears
B. The initial pattern evolves to a fixed finite size
C. The initial pattern grows indefinitely at a fixed rate
D. The initial pattern grows and contracts with time

Casti then conjectures the following theorem:

"Class A and B cellular automata have limit sets that form
regular languages. For most Class C and D automata, the
regular language complexity increases monotonically with
time so that the configurations obtained in the limit usually
do not form a regular language. Instead, the limit sets for
Class C automata appear to form context-sensitive languages,
whereas those for Class D automata seem to correspond to
general, unrestricted languages" (p. 71)

It's not clear from the references where Casti gets this
from: he refers to books by Davis & Weyuker (1983) and
Eilenberg (1974-76) and to a paper by Wolfram (1984) "Computation
Theory of CA's" Comm. Math. Physics 96, pp. 15-57

Philip Swann