FOM: an online survey of CAs

[vznuri@earthlink.net]

hi all;

john baldwin & I have been copiously exchanging emails,
attempting to wrap our brains around the current state
of CA research, figuring out the "theory-edge" of what
is known & unknown. I wanted to write up a quick overview
& pass it along to anyone else puzzling over the field
based on a quick online survey.

I ran into a nice survey article ref (a) by palash sarkar 
from 2000. he notes CAs are difficult field to survey & has
proceeded in fits & starts.  I think this is definitely
the place to start.

another reasonable starting point is the CA FAQ taken over
by tim tyler after a period of dormancy. his cell-auto
site is comprehensive with links elsewhere.

http://cafaq.com/

http://www.cell-auto.com/

alvy ray smith has been very active in CA research since
the early era, see his papers here

http://alvyray.com/Papers/PapersCA.htm

of course there is wolframs collected papers in ref (b) which
have many citations & are a nice survey. however the last
one in the book is dated 1986 & the field has moved significantly
since then.

there is a section on arXiv for CAs and lattice gases, but
the papers tend to be very oriented around physical modelling
& simulations.

http://www.arxiv.org/list/nlin.CG/recent

it looks like wolframs own journal, complex systems,
has carried the torch of serious CA research during the 90s
while there was not so much research elsewhere. pushed
forward by a small dedicated band of adherents. its a treasure
trove for CA analysis & I found many key articles which I cite 
below with abstracts, which are available & searchable online
(not sure about articles though).

http://www.complex-systems.com/

http://www.complex-systems.com/Archive/


CA classification
---

re: wolframs classification of CAs into 4 types.
the original idea was always given as qualitative & wolfram never 
came up with definitive, formally precise categories. 
his classification scheme was meant to loosely follow 
ideas from dynamical systems (typically specified by
differential equations), w.r.t limit points, 
limit cycles, chaotic/strange attractors.
so it has a reasonably solid mathematical rationale, background,
and origination.

apparently many researchers since wolfram are fully aware 
of the fuzziness of the wolfram categories & have attempted to hammer 
out more formal criteria. 
researchers have indeed linked up discrete CAs to continuous 
dynamical systems via bridge or transfer theorems. ref (d) from
the current issue of complex systems seems esp apropos & relevant.
however there is at least one negative result that
"Evolutions of cellular automata (CA) cannot be approximated by
the superpositions of real continuous functions." see ref (c)

ref (j) reveals that determining the classification of the CA within
wolframs categories must be undecidable in general.

ref (e) looks at "orbits" in general, another idea borrowed
from dynamic systems theory.

ref (l) looks at the description of limit sets of CAs based 
on formal languages.

there is some neat research that has related CA rules to groupoid
analysis, ref (f). imho it is again very solid evidence of the very
sophisticated properties of CAs to refute any beliefs by
hard-core mathematicians they are merely toy playthings not
worthy of serious consideration--i.e. quite to the contrary, its a vast
and promising terra incognita waiting to be mapped 
and joined into existing theory.

I suspect this is related to a deep theorem called the
"krohn rhodes decomposition" from computational complexity theory,
an obscure but important formulaton that (roughly) allows factoring 
and decomposition of FSMs in the same way that groups are factored
for insights into fundamental structure.

ref (i) gives further analysis with group and semigroup algebraic structures
for 90 elementary 1D CA rules.

ref (n) is somewhat similar, but shows how group properties of some
CAs (an important class called "linear" which allows "superpositions")
allow them to be very efficiently simulated, much faster than
the naive implementation.

ref (g) looks at another alternative classification system. there are likely
to be many categories associated with CAs in the same way that the
complexity hierarchy of algorithmic complexity theory has become
very intricate and multifaceted.


computation universality
---

john baldwin & I are attempting to hammer out a formal definition
of computation universality in CAs, & have made slow tangible
but hardwon progress in identifying some key difficulties & obscurities 
in the existing literature.  this is my rough summary.

1st, there is usually a concept of a "configuration" of finite
size that is surrounded by quiescent states (states that stay the
same if they are a "sea" of identical surrounding neighbors), 
and this is used to signify the instantaneous description 
of the TM at a given point in the cellular automata evolution. 
a single transition of the TM would be mapped out in a 
period of say [n] steps of the CA.

but we cannot be too strict. in some implementations [n] may vary
during the computation a bit depending on the implementation. 

for true universality, i.e. computing a function from input to
output rather than merely recognizing a language,
we need to worry about input and output
encodings of the analog of the TM "tape" onto the CA, the issue
that john baldwin raised. sometimes these can be encoded as maybe 
n-cell patterns for each binary digit.

however it appears there are
implementations of turing completeness such as the cook-wolfram CA110
proof that do not rely on a finite configuration surrounded 
by quiescent states. instead we have something
like what baldwin & I have been calling a "wallpaper" setup. there is a 
periodic wallpaper "background" that evolves in a periodic cycle 
around the finite configuration 
embedded in the middle of it. input conditions to the
CA require an infinite periodic pattern around the inputs.

halting is generally signified by what I have been calling a 
"steady state" result where the CA settles into a fixed pattern
with no evolution. but it seems to me that may be to strict & limiting;
& I have proposed the idea of "halt squares". a condition is specified for
a certain set of squares relative to the input, such that if a pattern
is detected there, we use that as our halting condition. so for
example a simulation could launch a glider that when detected in
some position, signifies the computation is complete. (and then
the output might be decoded.)

the bottom line, imho, is that any attempt to give definitions
for turing-universality of CAs are going to be fraught with possible
exceptions and may exclude CAs that can be reasonably construed
as such. hence imho any arguments or "proofs" that a given CA rule 
**cannot** be universal based on some criteria should be 
viewed with extreme caution and as fundamentally limited in their claims.
I presume there are creative exceptions nobody can possibly anticipate.


glider/soliton theory
---

in continuous systems, a self-similar, self sustaining & propagating
moving structure is called a "soliton" 
and there is some very elegant mathematics
on them. it looks to me like the CA equivalent & analog is what is
called a "glider". I can easily see that a nice general glider
theory is hidden in the existing literature &
seems to be waiting to be invented & mapped out.

it looks to me that based on the FSM transducer techniques 
applied in wolframs "computation theory of cellular automata",
there is a fairly straightfoward algorithm that can find 
all gliders of size [n] or less, of period [m] or less.
(p.169 of ref (b))

gliders seem to be analogous to what are called "invariant sets"
contained in "limit sets"; see wolfram, p188, where he gives 
an "eigenvalue" like equation for determining them. it looks to me
like one can give a mathematical formalism such that gliders are
given as eigenvalues of an RL algebraic equation.

Ive worked with nice software for RLs/FSMs/transducers
for implementing ideas similar to these algorithms. 
from AT&T labs, FSM library. 

http://www.research.att.com/sw/tools/fsm/


other areas
---

here I will look at some of the more general theoretical results,
particularly modern findings from the 90s, in a somewhat random way.

I noticed that on p182 of (b), wolfram describes a link between
CA evolution and the riemann function (!) based on dynamical
systems theory.  this seems very deep to me & worthwhile of further
exploration, investigation, & elaboration.

ref (h) gives a "small" computation-universal 1D CA rule.

ref (k) looks at the relationship between formal languages and 
CAs. this is an area I am especially interested in & have looked
into myself because of its relationship to (automatic) theorem proving. 
basically, one can convert many theorems to questions in the form, 
"does this turing machine never halt on an input". 
this in turn can be translated to a question
about the language accepted by the TM, or the CA it can be translated
to. 

so determining a language associated with a CA can in fact be
related to automated theorem proving. some analysis along these
lines of using an FSM transducer is given in wolframs paper,
"computation theory of cellular automata", p169 in (b). 

I see a strong link between transducer mappings and CAs as partially
explored in wolframs paper. there is some work showing that determining 
fixed points of transducer mappings is a turing-complete problem
but currently it seems the literature is not yet married 
up in this area.  (see work by P.R.J. Asveld)

ref (m) applies fourier analysis (i.e. looks at the power spectra)
of the attractors related to 1D CAs describable by regular languages.
I believe there is some more general result waiting to be mapped out that
shows how a 1D CA mapping is analogous to a convolution in 
fourier transform theory.


the cook-wolfram ca110 proof
---

I finally broke down & bought wolframs $44, ~1250p
"new kind of science", ref (o). 
there is much to be said & Im sure much (cyber-)ink will be spilled 
in the future over its contents as it is slowly 
assimilated. however what absolutely
astonished me is that I am extremely hardpressed to find a 
SINGLE REFERENCE WHATSOEVER to any specific book or paper in
the entire monster tome!! it almost seems quite possible there is not a
single one at all!!

maybe 1/3 of the book is dedicated
to the index and "notes", but wolfram never actually cites any
papers or books, only names people & rough dates!! (in the style
of, paraphrased, 'undecidability results were mapped out in the 30s').


I wanted to say a little about the cook-wolfram proof. as far as 
I can tell, cook did possibly **all** of the "heavy lifting"
in devising and completing the proof,
but he merits only a footnote in wolframs presentation as wolfram's
plucky "young assistant" whom wolfram valiantly pushed forward despite
moments of severe doubt on the latters part in the overall objective
(quite diplomatically, no mention is made
of the master **suing** his youthful apprentice over the 
latters findings). 

nevertheless, there is indeed an almost complete 
presentation of the full mechanics of
the CA110 universality proof, along with the full 
mathematica code in the notes section
by which someone might theoretically piece together a full formal proof.
Id say its enough evidence to take the result at face value, but with the
understanding the full details are still not available.

see p674-690, p115-1116 for a sketch of the ca110 universality proof. it
seems to use the "wallpaper" technique combined with tag systems.
"this is a very remarkable result, and one which will turn out
to be crucial to the new kind of science that I develop in this book."

Id say wolframs version of the events is a very deft dancing and
weaving around the reality that the "remarkable result" should basically 
be credited to cook, who even went to the lengths of 
"developing a systematic computer design
system" for dealing with CA110 gliders,
based on wolframs **conjecture** that CA110 is universal.

based on his treatment of cook, wolfram is 
starting to remind me of two famous historical figures.
galileo was found not to have originally discovered much of what he presented
in his own works, consolodating prior material into a new coherent
whole but by erasing anybody else's names from the presentation. 

that was before the modern concept of scientific
attribution, but one nevertheless cannot escape the underlying quality of 
disingenuousness. the other similar figure was edison, who created a massive
laboratory of underling engineers and generally blurred the credit of their
discoveries as his own.

but proper scientific attribution is one of those areas of scientific
debate that never seems to go away.. a kind of eternal knot, like
scientific inquiry itself.



an open note to wolfram: 
---

I suggest if you truly want to create a "new kind of science" 
that brings other scientists on board (assuming that is actually
your motive & goal, although that's ambiguous and questionable based on 
your directions and actions), you might

(1) cite other scientific works in the standard way; you obviously
know how to do that in (b) but evaded it for some perplexing reason
in "new kind of science", 

(2) consider putting all the complex-systems journal articles
on CAs on the web for online download so that other researchers
can quickly familiarize themselves with the state-of-the-art and
follow the lead. (due credit to you for supporting them during
the 90s when few else were)

(3) come clean on the mathew cook imbroglio. explain to the scientific
community why you felt it necessary to sue him, even after his results
had been published on the web and were in the public domain. & let him 
publish the proof under his own name if he is truly the full creator.



references
---

(a) Palash Sarkar: A brief history of cellular automata. 
ACM Computing Surveys Volume 32, Issue 1 (2000), Pages 80-107. 

http://portal.acm.org/citation.cfm?doid=349194.349202

(b) Stephen Wolfram, cellular automata & complexity, collected papers.
addison-wesley publishing co, 1994.

(c) Cellular Automata and Continuous Functions: Negative Results
Yuri Ozhigov. complex systems, vol 10, #5


(d) complex systems, vol 13 #2

The Relationship between One-dimensional
Continuous Cellular Automata and One-dimensional
Nonlinear Dynamical Systems
Randall E. Rausch 

In this paper the relationship between systems of
real-valued, or continuous, one-dimensional cellular
automata (CA) and a corresponding one-dimensional
nonlinear dynamical system is investigated. The CA will be
defined in a periodic domain and will satisfy requirements on
the function used to assign new values; the corresponding
one-dimensional dynamical system will be derived from the
function used to assign new values. It is shown that the
qualitative behavior of the CA--the existence of a stable
orbit with the same value at all cells--is determined by the
corresponding one-dimensional system and the geometry of
the CA. 


(e) complex systems, vol 8 #6

Growing Patterns in One Dimensional Cellular Automata
Bruno Durand,Jacques Mazoyer

We study limit evolutions of cellular automata (CA) both theoretically and
experimentally. We show that either all orbits enter the limit set after less
than a finitely bounded number of states, or almost all orbits never enter
the limit set. We link this result with a classification of CAs according to
their limit behavior due to Culik et. al.: in the first case, the considered CA
belongs to class 1 while in the second case, it belongs to class 2. 

By experiments, we try to measure the convergence speed of orbits to
their accumulation points. We compute the maximum number of nested
growing segments in a space-time diagram representing a finite portion of
an orbit. We observe that, in the average case, this criterion depends only
on the CA and not on the configuration. We also observe two kinds of CA
with respect to our criterion which correspond to the intuitive notions of
chaos and regularity. We do further experiments to explain the fact that
the proportion of chaotic diagrams grows with the number of states of the
considered CA. 


(f) complex systems, vol 6 #3

Cellular Automata as Algebraic Systems
John Pedersen

Infinite cellular automata have been studied mostly using empirical and
statistical techniques, with some combinatorial analysis. Here we show
how concepts of universal algebra such as subdirect decomposition and
chains of varieties can be applied to their study. Cellular automata with
ultimately periodic behavior are shown to correspond to varieties of
groupoids. Relationships between these varieties are analyzed. 


(g) complex systems, vol 4 #3

The Structure of the Elementary Cellular Automata Rule Space
Wentian Li, Norman Packard

The structure of the elementary cellular automata rule space is
investigated. The probabilities for a rule to be connected to other rules in
the same class (intra-class), as well as rules in different classes
(inter-class), are determined. The intra-class connection probabilities
vary from around 0.3 to 0.5, an indication of the strong tendency for rules
with the similar behavior to be next to each other. Rules are also grouped
according to the mean-field descriptions. The mean-field clusters are
classified into three classes (nonlinear, linear, and inversely linear)
according to the ``hot bits" in the rule table. It is shown that such
classification provides another easy way to describe the rule space. 


(h) complex systes, vol 4, #3

Universal Computation in Simple One-Dimensional Cellular Automata
Kristian Lindgren, Mats G. Nordahl

The existence of computation-universal one-dimensional cellular
automata with seven states per cell for a transition function depending on
the cell itself and its nearest neighbors (r = 1), and four states per cell for
r = 2 (when next-nearest neighbors also are included), is shown. It is also
demonstrated that a Turing machine with m tape symbols and n internal
states can be simulated by a cellular automaton of range r = 1 with m + n +
2 states per cell. 


(i) complex systems, vol 3 #2

Algebraic Theory of Bounded One-dimensional Cellular Automata
N. Pitsianis, G. L. Bleris, Ph. Tsalides, A. Thanailakis, H. C. Card

A formal mathematical presentation of various algebraic properties of rule
90 elementary one-dimensional cellular automata (CA) with null boundary
conditions is given. The CA global rule transition matrix is given and its
characteristic polynomial is formally obtained. Mathematical relationships
between the CA register lengths and the orders of the corresponding group
or semigroup algebraic structures are derived. 


(j) complex systems, vol 2 #2

Undecidability of CA Classification Schemes
Karel Culik II, Sheng Yu

Stephen Wolfram introduced the use of cellular automata as models of
complex systems and proposed a classification of these automata based
on their statistically observed behavior. We investigate various properties
of these classes; in particular, we ask whether certain properties are
effective, and we obtain several somewhat surprising results. For
example, we show that it is undecidable whether all the finite
configurations of a given cellular automaton eventually become quiescent.
Consequently, it is undecidable to which class a given cellular automaton
belongs, even when choosing only between the two simplest classes. 


(k) complex systems, vol 3, #1

Formal Languages and Finite Cellular Automata
Mats G. Nordahl

A one-dimensional cellular automaton rule with specified boundary
conditions can be considered as acting simultaneously on all finite
lattices, which gives a mapping between formal languages. Regular
languages are always mapped to regular languages, context-free to
context-free, context-sensitive to context-sensitive, and recursive sets
to recursive sets. In particular, the finite time sets on finite lattices are
regular languages. The limit set on finite lattices (the periodic set) is
shown to be neither a regular nor an unambiguous context-free language
for certain additive rules with chaotic behavior, and for rules that can
simulate one of these additive rules through a finite blocking
transformation. The relation between cellular automata on finite and
infinite lattices is discussed. 


(l) complex systems, vol 1, #1

Formal Language Characterization of Cellular Automaton Limit Sets
Lyman P. Hurd

A formal language description of one-dimensional cellular automata limit
sets is given, and a series of examples illustrating several degrees of
complexity are constructed. The undecidability of membership of a string
in the limit set of a cellular automaton rule is proven. 


(m) complex systems, vol 1 #1

Power Spectra of Regular Languages and Cellular Automata
Wentian Li

The spatial structure of attractors produced by many one-dimensional
cellular automata can be described by regular languages. This paper gives
simulations and analytical results for the power spectra of such attractors.
The power spectra are Fourier transforms of autocorrelation functions
which are exponentially damped (sometimes with oscillations). The
characteristic length scale is related to nontrivial eigenvalues of the
arc-to-arc transition matrix in the regular language graph. 


(n)

http://www.arxiv.org/abs/adap-org/9701001

Quasi-Linear Cellular Automata
Cristopher Moore

Simulating a cellular automaton (CA) for t 
time-steps into the future requires t^2 serial
computation steps or t parallel ones. However, 
certain CAs based on an Abelian group,
such as addition mod 2, are termed ``linear'' because 
they obey a principle of
superposition. This allows them to be predicted efficiently, 
in serial time O(t) or O(log t)
in parallel. 

In this paper, we generalize this by looking at CAs 
with a variety of algebraic structures,
including quasigroups, non-Abelian groups, Steiner 
systems, and others. We show that in
many cases, an efficient algorithm exists even though 
these CAs are not linear in the
previous sense; we term them ``quasilinear.'' We 
find examples which can be predicted in
serial time proportional to t, t log t, t log^2 t, 
and t^a for a < 2, and parallel time log t, log t
log log t and log^2 t. 

(o) stephen wolfram, a new kind of science. 2002, wolfram media.