The Global Dynamics of Cellular Automata

The Global Dynamics of
Cellular Automata

An Atlas of Basin of Attraction Fields
of One-Dimensional Cellular Automata

by Andrew Wuensche and Mike Lesser

Table of Contents.
Foreword - by Chris Langton.
Preface -
Preface to the Second Edition
(both the First and Second Editions are out of print).

The entire book (with a few freehand corrections)
has been scanned and is availabe HERE in pdf format.

Also at Google books - full view


front cover - click to enlarge

back cover - click to enlarge

Color Plates and the original DOS software

The seven pages of color plates, showing 28 reconstructed examples of basins of attraction, can seen HERE.

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.

Reviews

Information about the First Edition:

The book is hardcover, 250 pages, published in 1992 by Addison-Wesley, Advanced Book Program, Reading, MA, in the Santa Fe Institute Studies in the Sciences of Complexity, Reference Volume I. ISBN: 0-201-55740-1. For information at SFI click HERE.

Related topics

Back Cover Text

The Global Dynamics of Cellular Automata introduces a powerful new perspective for the study of discrete dynamical systems. After first looking at the unique trajectory of a system's future, an algoritm is presented that directly computes the multiple merging trajectories of the systems past. A given cellular automaton will "crystallize" state space into a set of basins of attraction that typically have a topology of trees rooted on attractor cycles. Portraits of these objects are made accessible through computer generated graphics. The "Atlas" presents a complete class of such objects, and is inteded , with the accompanying software, as an aid to navigation into the vast reaches of rule behaviour space. The book will appeal to students and researchers interested in cellular automata, complex systems, computational theory, artificial life, neural networks, and aspects of genetics.

Table of Contents

Foreword - by Christopher Langton
Preface - to the First Edition
One: Overview
Two: Cellular Automata and the Basin of Attraction Field
2.1 Cellular Automata
2.2 The Basin of Attraction Field
Three: The Transition Function and Global Dynamics
3.1 General CA Parameters
3.2 Rotation Symmetry
3.3 Rule Clusters
3.4 Limited Pre-image Rules
3.5 The Reverse Algorithm
3.6 The Z Parameter
Four: Implications of Basin of Attraction Fields
4.1 Basin Field Topology and Rule Space
4.2 Mutation
4.3 Conclusion
Appendix 1 The Atlas Program
Appendix 2 Atlas of Basin of Attraction Fields
Appendix 3 Mutants
Appendix 4 The Rule-Space Matrix, n=3 Rules
References
Index

Foreword - by Chris Langton

There are a wide variety of methods for representing the behavior of dynamical systems. Perhaps the most familiar representation method is the traditional time-series plot, in which some observable variable of the system (e.g., angular position) is plotted on the vertical axis, with time progressing to the right on the horizontal axis.

Such time-series plots trace the behavior of a system through time from a specific initial state. Thus, such plots represent the behavior of a system "localized" to a particular initial state, and are referred to as "local" representations of behavior. In order to get a feeling for the "global" behavior of a system, behavior independent of any particular initial state, one can collect an ensemble of such time-series plots, each rooted at a different initial state, and superimpose them together in the same plot. For certain systems, such ensembles of local representations can, in fact, lead to useful insights into the global dynamics of the system.

However, the "state-space" representation, introduced by Poincare, provides a much clearer portrait of the global behavior of dynamical systems. In a state-space representation, the ensemble of all possible time series is captured in the notion of a vector-field on the state space: the "field of flow" imposed on the space of states by a particular dynamical rule. A great deal of insight can be gained into the behavior of dynamical systems by understanding specific behaviors in terms of the topological properties of their associated trajectories in state space.

Although much of the work in the state-space analysis of dynamical systems has been carried out in the context of continuous state spaces, many of the concepts and methods carry over to discrete state spaces. In a discrete state space, the flow field can be seen to be a graph, in which the states are the nodes and the "flow" is captured by the edges linking the nodes. Just as one may have fixed points, limit cycles, and chaotic attractors in continuous flow fields, one may have fixed points, cycles, and infinite chains in graphs (in the latter case, of course, the state space must be infinite). Concepts such as the degree of spreading of a local patch of the flow field in continuous state spaces have their analogs in the degree of convergence-or "in-degree"-of a node in the flow graph in discrete state spaces.

The study of Cellular Automata (CA) has proven to be a particularly rewarding vehicle for gaining insights into the behaviors and peculiarities of discrete dynamical systems. However, a good deal of the previous analysis of CA has been carried out via the equivalent of time-series perspective, in which various properties of the space-time diagrams of the evolution of CA's from specific initial states are investigated.

This Atlas presents a comprehensive overview and analysis of CA from the state-space perspective. Although explicitly treating CA, many of the observations and results derived here depend only on properties of the flow graphs themselves, and consequently should be equally valid when applied to the flow graphs for other discrete dynamical systems.

This Atlas, together with the associated program for generating and analyzing flow graphs, should prove to be an invaluable tool for pursuing, in the context of discrete dynamical systems, the kinds of insights that can only be obtained from a global perspective.

Santa Fe, New Mexico
November 21, 1991

Christopher Langton


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.

Preface to Second Edition

The "Global Dynamics of Cellular Automata" was published in 1992 by Addison-Wesley. The publisher was later taken over by Perseus Books. According to Perseus, in early 1999 all remaining copies of the book where destroyed. Perseus did this without notifying the authors or the Santa Fe Institute. Apart from the 1000 plus copies that were sold prior to the destruction, there are apparently no surviving copies. Normally, the "remaindered" copies become available when a book goes out of print.

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''.

Andrew Wuensche
Santa Fe, New Mexico, April 2000
andy AT ddlab DOT org

Return to Top
Last modified: Oct 2009