## Cellular Automata in General

The term 'cellular automaton' hints at the marriage of two concepts, automata and cellular space, the latter being essentially an infinite square lattice. Automata per se have been the subject of a vast amount of research into their computing powers, particularly the languages they produce or recognize. The theory of automata has been a core subject in computer science from the beginning. It must be stressed that finite automata have powers of computation that are severely limited in comparison with a fully programmable computer.

remaining seven possible inputs. Finally, although care is normally taken not to confuse tape symbols with state names, we are about to enter a context where they are identical.

### Finite Automata

A finite automaton consists of a finite set of states, an input tape and an output tape (which may be identical to the input tape, if desired). Time is divided into discrete units and, between ticks of the clock, the automaton remains in the same state. At each tick, the automaton enters a new state that depends on its current state and its input symbol. Normally we express the rules that govern this behavior in a table or a state-transitiuon diagram (Figure 1). The figure shows a simple finite automaton represented in both ways.

The state-transition diagram consists of three nodes labeled with state names and transition arrows between them. The corresponding table consists of two columns (one for each possible input symbol) and three rows (one for each state). Below the diagram and table is a schematic drawing of the automaton, basically a simple visual context in which to imagine its operation (see Figure 1).

The finite automaton pictured here has three states and always writes the same input symbol as it reads, making only one tape necessary. For example, in state zero, if the automaton happens to be reading a 1, it enters state zero, according to the state-transition diagram. (Simply follow the arc labeled 1.) According to the table, it does the same thing. (Simply examine the entry in column 1 and row 0.) Once the transition is complete, the clock advances by one tick and the input tape shifts past the read-head by one square.

The input symbols do not have to be fed to a finite automaton one cell at a time. For example, inputs might consist of triples, as in 010, 011, 111, etc., or even longer strings. In such an automaton, for example, there might be a transition from state 2 to state 5 if the input was 011, but the transition might well be to other states for the

State-transition diagram

Symbol

State 0 1 2

State 0 1 2

 0 2 2 0 0 1

State-transition diagram

State-transition table

1

1

0 1 1 1 1 0 0 1 0 0 0

Finite automaton with input tape

Figure 1 Table and diagram for a finite automaton.

### Definition and Examples of Cellular Automata

Although many variations exist, the basic cellular automaton consists of a large rectangular grid of squares (called cells), a clock that ticks, and a finite automaton. We imagine that each cell has a copy of that finite automaton in it. Although the same finite automaton inhabits each cell, the automata so embedded do not have to be in the same state. The input for each automaton is not on a tape, but in the neighborhood of surrounding cells. Depending on how the 'neighborhood' is defined, the inputs will be strings of four state labels or eight of them. An example of this particular kind of finite automaton is provided later.

In a cellular automaton all cells typically begin in state 0, except for a finite number that are in other states. The nonzero patterns that occur while a cellular automaton is running are called 'configurations'. At each tick of the clock, many of the cells enter a new state and a new configuration develops. It is natural to refer to the sequence of configurations that develop as 'generations'.

Perhaps the most famous cellular automaton to date is the one discovered by Cambridge mathematician John Horton Conway. He called it the Game of Life because it produced lifelike phenomena, as we shall presently see.

Conceptually, the space of Conway's Life is a two-way infinite grid of cells each of which can be in one of only two states, 'alive' or 'dead'. We will give these states the rather less exciting names of '0' and '1'. In this particular cellular automaton, each cell is considered to have eight neighbors, the four cells adjacent to the sides of the square plus the four cells adjacent at the corners. A cell in state 0 at a given tick of the clock will remain in state 0 at the next tick unless it has three living neighbors presently. In that case it will enter state 1 at the next tick, coming 'alive', so to speak. A cell that is currently in state 1 will remain in state 1 at the next tick unless it has fewer than two neighbors in the state or more than three. Conway likens these rules to starvation (fewer than two living neighbors) or overcrowding (more than three).

These relatively simple rules astonished the mathematical and computing communities when first published in the journal Scientific American in 1970. No one would have predicted that such simple rules could lead to such complicated (and lifelike) behavior.

Figure 2 shows a simple behavior of the Life cellular automaton in which an initial configuration of five cells in state 1 changes from one tick of the simulation clock to the next, turning into a somewhat larger configuration of

Figure 2 Six generations.

nine cells in state 1 after five ticks of the clock. One can choose a particular cell in any of these stages and verify that its state in the next generation is the direct result of the appropriate rule as applied to the current generation.

An important feature in the Game of Life is the existence of 'gliders', self-perpetuating patterns that 'glide' across one's screen. Figure 3 shows the four consecutive configurations that constitute a glider. It will be noted that with every four generations, the glider has moved one cell diagonally in a direction that is determined by the orientation of the glider.

There is even a large configuration that produces gliders, requiring 30 generations for each glider to appear.

Even in the relatively simple milieu of a square-grid cellular automaton, a huge variety ofrules is possible. The kind of rule used by Conway is called totalistic because state transitions are based on simple counts of neighboring cell states. However, totalistic rules account for only a tiny fraction of all possible rules, as applied to a particular space.

Totalistic rules can be easily implemented by a finite automaton in this context. For example, the totalistic rule for a cell in state 0 to enter state 1 requires that exactly three of the eight neighboring cells be in state 1. To manage this with a state-transition table is straightforward. If we number the neighboring cells in a fixed manner 1, 2,..., 8, the set of all strings in which exactly three 1s appear yield a list of transitions that one could begin as follows:

input 00000111 00001011 00001101 next state 1 1 1

Although cellular automata are generally conceived as inhabiting an infinite grid, the practicalities of finite computer memories impose a finite grid. To rid themselves of the boundary effects that this restriction inevitably imposes, many workers use a wraparound space in which opposite borders of the (finite) grid are identified, that is, counted as neighbors.

### Figure 3 Glider.

The underlying geometry of the cellular space need not be rectilinear. The cells may be hexagonal, for example, as in a honeycomb. (This style of cellular automaton has the advantage of having only one kind of neighbor, rather than two, as in the case of the square grid.) Nor is the underlying dimensionality of the underlying space restricted to just two dimensions. For example, there is a successful version of the Game of Life in three dimensions. In this version the cells are cubical.

The simplest possible cellular automata inhabit a linear (one-dimensional) space in which each cell has two neighbors, one to the right and one to the left. The rules for such automata are much simpler than for those having higher dimensions. In fact, for a two-state linear cellular automaton there are only four possible combinations for a neighborhood of two cells. Thus, the table would have at most four entries for each state. Yet even linear cellular automata may exhibit startling properties.

The most famous come from Stephen Wolfram, a physicist who became convinced that cellular automata amounted to a new paradigm for biological science and possibly for physics itself. Having devised a numbering scheme which encoded the many possible rule sets, Wolfram discovered Rule 30, as written according to Wolfram's scheme:

neighborhood 000 001 010 011 100 101 110 111 next state 0 11110 0 0

The pattern of 1's and 0's, when written in reverse order, yields the binary representation for 30.

This cellular automaton, when started with an initial configuration consisting of a single cell in state 1 (the rest being in state 0), produces a succession ofgenerations that appear to be essentially random, as in the accompanying illustration, which tracks a mere 12 generations (Figure 4).

To this point deterministic rules have been assumed. The state of each cell depends on its own current state, as well as the states of its neighbors. The same configuration of states always gives rise to the same next state in a deterministic cellular automaton. In a probabilistic cellular automaton, the next state of a cell depends on probabilities associated with various configurations of its neighbors.

In general, probabilistic rules have the same form as deterministic ones except that the general statement would change from

Under the conditions X the next state is Y

Under the conditions X the next state is Y with probability p.

### Cellular Automata as Ecological Models

It is frequently useful, in building a cellular automaton model, to generalize the rules by making certain numbers available only at runtime. For example, the model might involve totalistic rules but with the totals treated as variables. In other words, the automaton might specify that when a cell is in a certain state, it will enter state 3 if n of its neighbors are in state 2. At run time, the user of

### Figure 4 Output of Rule 30.

the program may explore different behaviors by giving n a different value than he or she did last time. The probabilities used in probabilistic rules may also be made into variables, to be explored at runtime in much the same manner. Such variables, set at runtime, are called parameters of the model.

One can analyze some cellular automata readily enough to make certain predictions about their behavior without using a computer. But with a computer, one can see the rapid development of configurations through time, experiment endlessly with initial configurations, watch their fates, and adjust rules and parameters to explore certain possibilities.