Cellular Automata

Introduction
The increasing prominence of computers has led to a new way of looking at the world. This view sees nature as a form of computation. That is, we treat objects as simple computers, each obeying its own set of laws.

The "cellular automaton" extends this analogy to provide a way of viewing whole populations of interacting "cells", each of which is itself a computer (automaton). By building appropriate rules into a cellular automaton, we can simulate many kinds of complex behaviour, ranging from the motion of fluids governed by the Navier-Stokes equations to outbreaks of starfish on a coral reef.

Definition
A cellular automaton is an array of identically programmed automata, or "cells", which interact with one another.

The arrays usually form either a 1-dimensional string of cells, a 2-D grid, or a 3-D solid. Most often the cells are arranged as a simple rectangular grid, but other arrangements, such as a honeycomb, are sometimes used.

The essential features of a cellular automaton ("CA" for short) are:

its STATE is a variable that takes a different separate for each cell. The state can be either a number or a property. For instance if each cell represents part of a landscape, then the state might represent (say) the number of animals at each location or the type of forest cover growing there.

its NEIGHBOURHOOD is the set of cells that it interacts with. In a grid these are normally the cells physically closest to the cell in question.Here are some simple neighbourhoods (cells marked n) of a cell (C) in a 2-D grid ...

             n                              n n n                    n n n n
          n C n                          n C n                   n C n n n n
              n                             n n n                    n n n n

its PROGRAM is the set of rules that defined how its state
changes in response to its current state, and that of its neighbours.

Example - Fabric patterns

Imagine a CA consisting of a line of cells as follows:

states : 0 or 1
neighbourhood : the two adjacent cells N C N
rules : the following list shows the new state of a cell for each possible local "configuration", i.e. arrangement of states for the cell and its two neighbours. Because there are two possible states ( 0 or 1) for each of 3 cells, there are 2^3 = 8 rules required. Here they are

                                0 0 0       ->     0                     1 0 0     -> 1 
                                0 0 1       ->     1                     1 0 1     -> 1
                                0 1 0       ->     1                     1 1 0     -> 0
                                0 1 1       ->     0                     1 1 1     -> 0

Suppose that we start with just a single cell in state 1. Then here is how the array will change with time (here "." denotes 0 for clarity).

Time 0 : . . . . . . . . . . 1 . . . . . . . . . . .
Time 1 : . . . . . . . . . 1 1 1 . . . . . . . . .
Time 2 : . . . . . . . . 1 . . . 1 . . . . . . . . .
Time 3 : . . . . . . . 1 1 1 . 1 1 1 . . . . . ..
Time 4 : . . . . . . 1 . . . 1 . . . 1 . . . . . . .
Time 5 : . . . . . 1 1 1 . 1 1 1 . 1 1 1 . . ..
Time 6 : . . . . 1 . . . 1 . . . 1 . . . 1 . . . ..


Properties

Self-organization. Notice that when we plot the successive states as shown in the above example a pattern emerges. Even if the line of cells starts with a random arrangement of states,
the rules force patterns to emerge (Fig. 1).

Life-like behaviour. Empirical studies by Wolfram and others show that even the simple linear automata above behave in ways reminiscent of complex biological systems. For example, the fate of any initial configuration of a cellular automaton is either:

1. to die out;

2. become stable or cycle with fixed period;

3. to grow indefinitely at a fixed speed;

4. to grow and contract irregularly.


"Thermal" behaviour. In the above example of a linear automaton 6 of the 8 rules forced a change in the state of the cell concerned. In general, models that force a change of state for few configurations tend to "freeze" into fixed patterns, whereas models that change the cell's state in most configurations tend to behave in a more active "gaseous" way. That is fixed patterns do not emerge.

The game of LIFE
The game LIFE, invented by the Cambridge mathematician John Conway, is a simple 2-D analogue of basic processes in living systems. The game consists in tracing changes through time in the patterns formed by sets of "living" cells arranged in a 2-dimensional grid. Any cell in the grid may be in either of two states:

"alive" or "dead". The state of each cell changes from one generation
to the next depending on the state of its immediate neighbours. The
rules governing these changes are designed to mimic population change:

FIGURE 2

Figure 2a The game LIFE. Some simple patterns that die (left); remain constant (centre); and cycle (right). The pattern at lower right, called a "glider", not only cycles but
also glides diagonally across the grid of cells.

Figure 2b Self-organization in the game LIFE. The random initial configuration of cells (left) reduces to constant and cycling elements after 2500 generations (right).

1. A living cell with only 0 or 1 living neighbours dies from isolation.

2. A living cell with 4 or more living neighbours dies from overcrowding.

3. A dead cell with exactly 3 living neighbours becomes alive.

4. All other cells remain unchanged.

The behaviour of LIFE is typical of the way in which many cellular automata reproduce features of living systems. That is, regularities in the model tends to produce order: starting from an arbitrary initial configuration, order (i.e. patches of pattern) usually emerges fairly quickly. Ultimately most configurations either disappear entirely or break up into isolated patterns that are either static or else cycle between several different forms with a fixed period.

An application to simple forest models

Cellular automata models of landscapes consist of fixed arrays in which each cell represents an area of the land surface. The states associated with each cell correspond to environmental features, such as coral cover or topography. This approach is compatible with both pixel-based satellite imagery and with quadrat-based field observations. It also enables processes that involve movement through space (e.g. fire, dispersal) to be modelled in "natural" fashion.

To see how easily the cellular automaton idea can be brought to bear on real systems, consider a system whose states are of the form (s,t), where t denotes "time since fire burned out the cell" and s takes one of the values: "bare earth" (E), "grass" (G), "woodland" (W), and "closed forest" (F). Define state transitions rules as follows:

            (E,   0)      ->      (G, 1),
            (G,   4)      ->     (W, 5),
            (W,49)      ->     (F, 50),
             (s,     t)     ->      (E, 0), if a fire ignites nearby
                            ->       (s,t+1), otherwise

Starting with an arbitrary "landscape", consisting of a 2-D grid of cells in random states, the rules quickly produce patterns (Fig. 3). For instance, "forest zones" quickly develop, even though the model contains no assumptions about the environment or site preferences of the vegetation. Admittedly, this model is a mere caricature of true forest succession, but it is only a short jump to management models taking (say) satellite data as inputs.

Further reading
Bossomaier, T.J. & Green, D.G. (1998).
Patterns in the Sand - Computers, Complexity and Life. Allen and Unwin.

Coveney, P. and Highfield, R. (1995).
Frontiers of Complexity. Faber and Faber, Chapter 6.

On-line resources
The Game Life
ftp://life.csu.edu.au/pub/complex/alife/dr-life.zip
Complexity On-line
http://life.csu.edu.au/complex/
Complexity International
http://www.csu.edu.au/ci/
Complexity Virtual Library
http://life.csu.edu.au/vl_complex/
Search the Web for related information and resources.
Complexity Virtual Library - Cellular Automata
http://life.csu.edu.au/vl_complex/0CellularAutomata.html
Copyright:
David G. Green,
Environmental and Information Sciences, Charles Sturt University