Second Edition
Discrete Dynamics Inc., Santa Fe, NM
250 pp, $20.00 (US softcover)
email: andyw@cybermesa.com

Review by Stuart Kauffman

There is a scientific romance behind this fine book. Outsiders often make startling contributions to a field. In this case the outsiders were Andrew Wuensche, a successful architect in London, and his friend, Mike Lesser, with a background in industrial automation, and robotics. Yet these two, not knowing that the problem they were attacking, that of finding all the predecessor states to any state in a cellular automaton, had been intuitively deemed virtually insoluble by the academic insiders in the field, insiders that include this reviewer. Andy and Mike attacked and nailed the problem. This book records their success, provides analytic insights that trained mathematicians working in the field missed left and right, and constitutes the only atlas of the basins of attraction fields of one dimensional cellular automata. Wuensche's stunning DDLab program has grown out of this initial effort.

One dimensional cellular automata consist in a line of "cells" or "nodes", typically arranged in a circle to achieve periodic boundary conditions. Each node is capable of a number of discrete states, S, where S is often taken to be 2, "on" and "off". In this binary case, each node realizes a Boolean function with one input from itself and additional inputs. A typical case considers a node with inputs from itself and its immediate left and right neighboring nodes, a 3 node neighborhood. Another common case considers a note with inputs from its two neighbors to the left and two neighbors from the right, a 5 node neighborhood. Each node is assigned one of the possible Boolean functions on its inputs. For standard cellular automata, all nodes are governed by the same Boolean function. Time occurs in synchronous discrete steps, at each of which each node looks at the values, 1 or 0, of its inputs, consults its Boolean function, and assumes the proper next value, 1 or 0. If the ordered set of values in a ring of N nodes is defined as a state of the system, then at each moment the system passes from a state to a successor state. Over a succession of time moments the system traces out a trajectory in its state space of all 2 raised to the Nth power combinations of activities of the N nodes. Since there are a finite number of states, the system eventually hits a state previously encountered. Since the system is deterministic and has no inputs from outside the system, the cellular automaton must then trace out a recurrent "state cycle" attractor. The state cycle is called an attractor because, generically, there is a basin of states, each state lying on a trajectory that flows to the attractor state cycle or lies on that state cycle itself. Thus, the basins of attraction partition the state space into disjoint sets, each with states that flow to a single state cycle. Among the states on trajectories are "garden of Eden" states which have no predecessor states.

Examination of cellular automata, and their more disordered cousins, the first class consisting in networks with more or less random wiring diagrams, but with all nodes realizing the same Boolean function, pioneered by C. Walker, and Random Boolean Nets, in which each node is assigned its inputs and its Boolean function at random, which I introduced some thirty five years ago, has largely been limited to the temporally forward "integration" of the dynamics of such networks. The process is simple enough, one constructs a network, picks an initial state, and lets the network step forward until a state cycle is found. Many features can be examined with the use only of forward dynamics, including estimates of the numbers of basins of attraction, the size distribution of attractor state cycles, the cascading consequences of transiently perturbing the activity of single nodes, and so forth.

While the temporally forward direction of simulation and analysis has yielded powerful results, there is a major gap: How is one to map out the entire basin of attraction portrait of the cellular automaton, or random Boolean network? If one is using the forward dynamics, this would require starting the system at each of its 2 raised to the N possible states. For even modest N, this is simply impossible.

What Andy and Mike solved was the problem, noted above, of finding all the predecessor states for any state in a one dimensional cellular automaton. This breakthrough meant that one could now efficiently trace backwards from a state cycle, back up each transient sequence of states, to all the garden of Eden states that constitute the "headwaters" of the basin of attraction flowing to that state cycle. Since the algorithm to accomplish this is orders of magnitude more efficient that trying all initial states, this has meant that Andy and Mike could characterize ALL the basins of attraction for one dimensional cellular automata. No one else has done this.

The resulting Atlas is something of a tour-de-force. First Wuensche and Lesser derive analytic approaches to define and characterize the temporally inverse problem. They discuss rule clusters, limited pre-image rules, the reverse algorithm, and introduce the "zed" parameter, then they turn to producing the Atlas itself, both for the 88 different equivalence classes of Boolean functions of K = 3 inputs, given by a node and its left and right neighbor nodes and for some of the K = 5 rules. Naturally, the basins of attraction can depend upon the number of nodes on the ring of nodes. The Atlas covers rings of sizes N = 1 through N = 15. In addition they include not only the Atlas program itself, but an analysis of the effects of mutants on basins of attractions.

A particular treat in the Atlas is a set of stunningly beautiful basins of attraction from different specific cellular automata that seem never to fail to strike the viewer. A set of these, in fact, happens to hang in the hallways of Bios, the company I started in Santa Fe. I often feel that their beauty equals that of the jewelry created in this gifted small city.

What is the proper role and impact of such an atlas, plus the capacity to solve the "time reverse" problem? With respect to the latter, Wuensche and Lesser have opened the door to the detailed study of basins of attraction in modestly large cellular automata, and the trajectory structure even of large cellular automata. Wuensche has gone on to generalize their approach to random Boolean networks in many useful ways, as reported in further publications. But what of the atlas itself. It represents a major effort that shows us, for the first time, the scale and diversity of patterns of activity of cellular automata in all their richness, the full panoply of basin portraits, sensitivity to rule and number of nodes in the ring, distribution of numbers of basins and characters of those basins among the 88 equivalence classes for K = 3 rules, and some of the "totalistic" K = 5 rules. An atlas is, at a minimum, a compendium of information, and a source of data and inspiration for those seeking to understand this profoundly simple, yet profoundly rich class of mathematical structures. If complexity science is anything, it is the search for patterns and laws in the rich diversity of behaviors that systems built up out of many simple components, from cellular automata to immune networks and ant colonies, achieve.

Wuensche and Lesser have done us all a very substantial service. The outsiders, now insiders, have done it again, enriching a field that they had no "right" to succeed in with such tenacity and brilliance.

Note: Color plates can be found at here. Further information about the book can be obtained at here.

Reviewed by Stuart Kauffman, The Bios Group, LP, 317 Paseo de Peralta, Santa Fe, NM 87501