The Global Dynamics of 

The original DOS software, which was included on diskette with the
book, is availabe in the file atlas.zip
HERE,
(zipped with pkzip/pkunzip).
The Operating Instructions are in the book.
Preface  to the First Edition
The study of the dynamical behavior of cellular automata (CA) has become
a significant area of experimental mathematics in recent years. CA
provide a mathematically rigorous framework for a class of discrete
dynamical systems that allow complex, unpredictable behaviour to emerge
from the deterministic local interactions of many simple components
acting in parallel.
Such emergent behavior in complex systems, relying on
distributed rather than centralized control, has become the
accepted paradigm in the attempt to understand biology in terms of
physics (and vice versa?), encompassing such great enigmas as the
phenomena of life and the functioning of the brain. Rather than
confronting these questions head on, an alternative strategy is to pose
the more modest question: how does emergent behaviour arise in CA, one
of the simplest examples of a complex system.
In this book we examine CA behaviour in the context of the global
dynamics of the system, not only the unique trajectory of the system's
future, but also the multiple merging trajectories that could have
constituted the system's past.
In a CA, discrete values assigned to an array of sites change
synchronously in discrete steps over time by the application of simple
local rules. Information structures consisting of propagating
ensembles of values, may emerge within the array, and interact with each
other and with other less active state configurations. Such emergent
behaviour has lead to the notion of computation emerging
spontaneously close to what may be a phase transition in CA
rule space. Emergent behaviour in 2D CA has given rise to the new field
of artificial life.
In the simpler case of 1D CA, a trace through time may be made which
completely describes the CA's evolution from a given initial
configuration. This is portrayed as rows of successive global
states of the array, the spacetime pattern. Spacetime
patterns represent a deterministic sequence of global states evolving
along one particular path within a basin of attraction, familiar
from continuous dynamical systems. In a finite array, the path
inevitably leads to a state cycle. Other sequences of global states
typically exist leading to the same state cycle. The set of all possible
paths make up the basin of attraction. CA basins of attraction are thus
composed of global states linked according to their evolutionary
relationship, and will typically have a topology of branching trees
rooted on attractor cycles.
Other separate basins of attraction typically exist within the set of
all possible array configurations (state space). A CA will, in a
sense, crystallise state space into a set of basins of attraction, known
as the basin of attraction field. The basin of attraction field
is a mathematical object which, if represented as a graph, is an
explicit global portrait of a CA's entire repertoire of behaviour. It
includes all possible apacetime patterns.
The study of basin of attraction fields as a function of CA rule
systems, and how the topology of the fields unfold for increasing array
size, may lead to insights into CA behaviour, and thus to emergent
behaviour in general. This book shows CA basin of attraction fields as
computer graphics diagrams, so that these objects may be as easily
accessible as spacetime patterns in experimental mathematics.
Construction of basin of attraction fields poses the problem of finding
the complete set of alternative global states that could have preceded a
given global state, referred to as its preimages Solving this
problem is recognized as being very difficult, other than by the
exhaustive testing of the entire state space. Exhaustive testing becomes
impractical in terms of computer time as the array size increases beyond
modest values. Consequently, access to these objects has been limited.
This book introduces a reverse algorithm that directly computes
the preimages of a global state, resulting in an average computational
performance that is many orders of magnitude faster than exhaustive
testing. Two computer programs using the algorithm are described (and
enclosed), to draw either basin of attraction fields or spacetime
patterns, for all 1D, binary, 5neighbour CA rules, with
periodic boundary conditions, and for the subsets of these rules,
the 3neighbour rules, and the 5neighbor totalistic rules.
An atlas is presented (Appendix 2) showing the basin of attraction
fields of all 3neighbour rules and all 5neighbour
totalistic rules, produced using the program, for a range of array
lengths. The atlas may be used as an aid to navigation in exploring the
global dynamics of the 2^{32} rules in 5neighbour rule space.
The book is divided into two parts. The first part (Chapters 1 through 4)
gives the theoretical background and some implications of basin of
attraction fields. The second part consists of appendices including the
atlas and computerprogram operating instructions.
Chapter 1 is an overview of the contents of the book.
Chapter 2 describes how CA global dynamics are represented by basin of
attraction fields.
Chapter 3 looks in detail at CA architecture and rule systems, and the
corresponding global dynamics. It is shown that ordered
architecture and periodic boundary conditions impose
restrictions on CA evolution in that rotational symmetry (and
bilateral symmetry for symmetrical rules) are
conserved. The rule numbering system and equivalence classes are
reviewed. Symmetry categories, rule clusters, limited
preimage rules, and the reverse algorithm are
introduced. The Z parameter, which reflects the degree of
preimaging, or the convergence of dynamical flow in state space, is
introduced.
Chapter 4 looks briefly at some implications of the above on current
perceptions of the structure of rule space. The Z parameter is suggested
as the mechanism underlying the lambda parameter . A relationship
between the Z parameter, basin field topology, and rule behaviour
classes, based on the atlas, is proposed.
The idea of the rule table as genotype and the basin of
attraction field as phenotype is examined. Mutating the
rule table is found to result in mutant basin field
topologies. Examples of sets of mutants are presented in Appendix 3.
We hope that the atlas of basin of attraction fields, and the program
for exploring further into rule space, will provide new opportunities
for CA research.
The copyright was eventually returned to the authors. As there is still demand for the book, I decided to reprint a Second Edition. The second edition is a straight copy of one of the original books, with just a few freehand corrections of typographical and other errors that have come to light, see the corrections index below. The seven pages of color plates, which led some people to call the original a "coffee table book", are omitted to save cost. However, the same reconstructed images can be seen in color at www.cogs.susx.ac.uk/users/andywu/. The original color cover is also now black and white, with a few changes.
There have been quite a few developments of the ideas first presented in the book, for example generalizing the methods to Boolean networks, applications to neural and genetic networks, and methods for classifying cellular automata automatically. Publications on this work can be found in the references below. However, many of the book's original ideas, such as rotation symmetry, rule clusters, limited preimage rules, mutations and the rulespace matrix, have not been repeated in other publications, and others such as the reverse algorithm and the Zparameter are explained at length only in the book. Further, the book is the only place to browse the "Atlas of Basin of Attraction Fields" itself, so the book remains the only source for most of this material.
The section "The Atlas Program" remains in the second edition, describing the DOS software which was included on diskette with the book. This original software can now be downloaded from www.santafe.edu/~wuensch/gdca.html. Note that this software has been superseded by "Discrete Dynamics Lab" (DDLab), a much more powerful and versatile tool for studying discrete dynamical networks, running on Unix, Linux and Irix as well as DOS. This is available from www.ddlab.org.
Many people have commented, why not put the whole book on the web. Good idea, but as it was produced in the days of cut and paste, that's not so easy. Anyway, I think its still useful to be able to flip through a hard copy of "the Atlas''.
Andrew Wuensche
Santa Fe, New Mexico, April 2000
andy AT ddlab DOT org