© Copyright JASSS

  JASSS logo

The Global Dynamics of Celullar Automata: An Atlas of Basin of Attraction Fields of One-Dimensional Cellular Automata

Andrew Wuensche and Mike Lesser
Santa Fe, NM: Discrete Dynamics Incorporated
2000
Cloth: ISBN 0-201-55740-1

Order this book

Reviewed by
H. Van Dyke Parunak
ERIM, P.O. Box 134001, Ann Arbor, MI 48113-4001, USA.

Cover of book

This volume originally appeared in 1992 in the Santa Fe Institute's series "Studies in the Sciences of Complexity," published by Addison-Wesley. According to the first author's preface to the second edition, the title was taken over by Perseus Books, which in early 1999 took the volume out of print and destroyed all unsold copies, leaving only 1000 or so already sold copies in existence.

It is understandable that many publishers are not in the position to maintain a volume that sells only 1000 copies in seven years. It is also understandable, particularly for some more esoteric titles, that sales volume is an inadequate barometer of a book's merit. With well-merited confidence in the enduring value of their work, Wuensche and Lesser have reprinted the volume to keep it in circulation. The second edition differs from the first in four ways:

  1. It is entirely in black and white, not in colour (though reproductions of colour plates from the original edition are available on a web site).
  2. Three introductory pages describe the history of the book, bring the bibliography up to date and list corrections.
  3. Corrections to typos in the first edition are inserted freehand into the body of the book.
  4. Software for the book is no longer included on diskette but available through a web site.

Since the second edition is a photographic copy of the original, its typographic quality is lower than one might expect. But researchers interested in the complex dynamics of multi-agent systems should be grateful that the book is still available, in any form.

The book is a major study of one-dimensional cellular automata, algorithms that define the temporal evolution of a finite string of symbols. This work uses n = 2 symbols {0,1}. The algorithm focuses attention on a single position in the string and a limited number of its neighbours (typically, one neighbour on either side, yielding a neighbourhood size k = 3). The value of the focal position at time t+1 will be a function of the values at time t of it and its neighbours. The same function (called the CA's "rule") is applied simultaneously to all locations in the string, and the ends of the "string" are considered connected to each other so that they do not present a discontinuity. This simple scheme is capable of generating a wide range of behaviours, depending on the function that maps the state of the neighbourhood at time t to the state of the focal position at time t+1. Various functions produce degeneration to a steady state, periodic patterns, noisy chaotic patterns and patterns intermediate between periodic and chaotic that have been hypothesised to support universal computation. Because of this richness, cellular automata are for complex systems theorists what E. coli are for the biologist: a system simple enough to manipulate experimentally, but complex enough to suggest insights for real-world problems.

It is in this spirit that the volume will be of interest to readers of JASSS. It is not relevant at the domain level, for it does not discuss artificial societies or social systems explicitly at all. Nor is it relevant at the tool level. Two-dimensional cellular automata are adequate only for some simple social models (such as the Schelling model) and even these would not be possible in a one dimensional CA.

The lessons for social simulation are more subtle, though extremely important. This work highlights some critical general principles of complex adaptive systems in general and interacting multi-agent structures in particular. Though Wuensche and Lesser illustrate these principles in the context of models far simpler than social systems, there is growing evidence that principles of this sort transcend any particular application domain or modelling tool. Practitioners of social simulation, particularly adherents to the multi-agent approach, ignore them at their peril.

The subtitle introduces the main theme of the volume, that of "basin of attraction fields". Understanding this term requires us first to understand the two terms "attractor" and "basin of attraction":

Wuensche and Lesser are particularly interested in "Garden of Eden states," states that lie at the tip of a transient and cannot be produced from any other configuration. Their main technical contribution is a clever algorithm (long thought impossible by leading complexity scientists) for unwinding the evolution of a CA backwards. Before their algorithm, the only way to map out basins of attraction for CA was to sample various initial configurations and run them forwards. This algorithm greatly reduces the time required to explore a basin, and push back to Garden of Eden states. It enables them to map out exhaustively the basin of attraction fields for all two-state,three-neighbor CA. The first 60 pages of the book develop the algorithm, while the bulk of the remainder (the atlas proper) displays the resulting fields graphically.

Even in black and white, this volume has tremendous graphical appeal, and the pages of the atlas will repay careful browsing with an enriched sense for the range of stability and diversity that emerges from these simple structures. More generally, the volume holds some important lessons for modellers of social systems.

The concepts of attractors, transients, basins of attraction, and fields are applicable to any complex system, including a social simulation. They embody several important lessons:

The notion of reversing the CA and running it backwards to find transients and Gardens of Eden is a new perspective on a dynamical system. Sometimes knowing where one has come from is as important as knowing where one is going. Reversing a non-trivial social simulation is likely to be considerably more complex than reversing a CA, but the concept is a valuable one, and worth consideration by researchers in many different fields.

ButtonReturn to Contents of this issue

© Copyright Journal of Artificial Societies and Social Simulation, 2001