The Global Dynamics of
of One-Dimensional Cellular Automata
The original DOS software, which was included on diskette with the
book, is availabe in the file atlas.zip
(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 2-D CA has given rise to the new field of artificial life.
In the simpler case of 1-D 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 space-time pattern. Space-time 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 apace-time 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 space-time 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 pre-images 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 pre-images 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 space-time patterns, for all 1-D, binary, 5-neighbour CA rules, with periodic boundary conditions, and for the subsets of these rules, the 3-neighbour rules, and the 5-neighbor totalistic rules.
An atlas is presented (Appendix 2) showing the basin of attraction fields of all 3-neighbour rules and all 5-neighbour 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 232 rules in 5-neighbour 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 computer-program 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 pre-image 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 pre-image rules, mutations and the rule-space matrix, have not been repeated in other publications, and others such as the reverse algorithm and the Z-parameter 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''.
Santa Fe, New Mexico, April 2000
andy AT ddlab DOT org