Cellular Automata: A Discrete View of the World

I would bet most people saw a cellular automaton working before they had ever heard of cellular automata (CA). While I was in graduate school our Sun workstations ran a screen saver called "The Game of Life" created by John Conway. I knew little of this game, where colored cells were born, died, moved, and sometimes displaying flashing, periodic behavior. Yet this was my introduction to CA.

We have come a long way from seeing CA as a game to a full-fledged research area — an area that may explain the workings of the universe, hence the sub-title. And what better way to begin one's research than with this book.

There are many books on cellular automata (see, for example, Wolfram or Ilachinski) but few books give readers, especially at an undergraduate level, an introduction that is easy and fun to read, covers the topic in the right amount of detail, and encourages immediate play with the subject. Schiff's book does all these things.

The book begins with a short introduction to concepts such as Turing machines, logic gates, and dimension measures (for example, fractal and information), which will later be applied to CA. The reader will find that CA can implement logic functions and act as a universal computer. The text digresses a bit to discuss dynamical systems which is interesting but not developed much in connection to CA.

By chapter three the book is finished with preliminaries and we come to one-dimensional CA. In general, a CA is a rule set applied to a grid with cells that are on or off, black or white, alive or dead (say, Conway's game). The CA begins with an initial condition and then the rules are applied at each time step to the grid so that, say, black squares may change to white or white to black, each change depending on the state (color) of the cell and the states of nearby cells. As time goes and the CA runs, patterns develop. This is how we usually think of a CA. A one-dimensional CA is where the next state of cell depends on its current state and on neighboring cells to the left and right. Pictures show the cells and their states along the horizontal dimension with time moving top to bottom. Schiff gives examples and each example is well-done with graphics and text that beckons the reader to program his own CA code. The discussion is complete with details on boundary conditions and transition functions, both necessary for your simulations.

A fascinating concept related to CA is reversibility. That is, can we let a CA run, then with the final state, apply the rules in reverse and go back to where we started? If we can, we have a reversible system. Some CA are reversible and some not. I leave you to read the details.

Chapter four expands our thinking as we move to two-dimensional CA (the Game of Life is a two-dimensional CA) where the next state of a cell depends not just on its neighbors left and right, but up and down, too. For simple neighborhoods of cells within one unit from a given cell, the number of transition functions is astronomical so we are led to believe that CAs with these transitions are quite diverse and interesting. It's not clear if that's true or whether these vast numbers of transitions functions exhibit boring behaviors.

Chapter five is a discussion of applications such as neural cells, social interaction, the iterated prisoner's dilemma, bacterial growth, sea shell patterns, snow crystals, sand piles (see Per Bak, How Nature Works for a wonderful discussion of sand piles and self-organized criticality), among others. If you aren't attracted to CA by this time (for me, the fascinating behavior from simple rules is enough), then the applications will convince you of the value of CA.

Finally, the last chapter addresses complexity, which is part of the phenomenon of emergent behavior. Emergent behavior arises from the interactions of simple automata such as agents, whose individual behavior is based on simple rules but the behavior of all agents is impossible to predict. Real life examples include ant colonies and bee hives, even people. These concepts arise naturally from CA. Schiff does an admirable job of introducing the ideas to newcomers.

In sum, this book provides an excellent introduction to the concepts of CA, shows the reader how to program CA, and provides motivation for further work through applications and the discussion of complexity. I recommend it to anyone starting to learn this fascinating science.

David S. Mazel received his doctorate from the Georgia Institute of Technology in electrical engineering and is a practicing engineer in Washington, DC. His research interests are in the dynamics of billiards, signal processing, and cellular automata.