• Contribute
• What's New
• Submit News

One and two-dimensional cellular automata (CAs) are very simple agents that obey a small number of rules. Often though, these rules lead to highly complex and emergent behaviour that can be used to study various real-life phenomena.

This essay will explore basic examples of 1D and 2D CAs and their significance.

One Dimensional

One dimensional CAs are the simplest. Each row of cells is dependent on the row above. For example, a cell may be dependent on the states of the three cells above it (immediately above, above-left, above-right). States may comprise of a variety of intermediary states, but for the moment we will look at simple "alive" or "dead" (binary).

Imagine a rule table, where each rule is specified according to the three cells above: {(x-1, y-1), (x, y-1), (x+1, y-1)}. An example of such a rule table might be:

Graphically, this could be illustrated using a diagram like this:

Simple rules, but look at the results! Even simple rules like these can produce incredibly complex, self-similar images reminiscent of the patterns found on sea shells. Below are three more partial thumbnails of other examples of 1D cellular automata. All these patterns use an expanded neighbourhood of 5, giving 32 possible rules:

Classes I and III are not terribly interesting, but classes II and IV have very interesting properties that are beyond the scope of this introductory essay but, suffice to say, it is probable that there exists a class IV pattern that will act like a Universal Turing Machine, as well as numerous other traits. Gary William Flake briefly covers a few of these ideas in The Computational Beauty of Nature.

Totalistic and Continuous CA

Two other similar types of one-dimensional cellular automata are totalistic and continuous CAs. Totalistic cellular automata expand on simple 1D CAs by adding an additional state (often rendered as grey). New states are calculated by taking the average state of the above neighbours which in turn determines the new state. Just as standard rules can be encoded using base-2, totalistic CA rules can be encoded using base-3 (for example, 777 = 1001210).

Continuous CAs extend the number of states even further. Like totalistic CAs, new states are calculated by taking the average of the above states, adding an offset and taking the fractional part of the result. For example, if the offset is 0.9 and the above neighbours are 0.722, 0.833 and 0.722 respectively, the new state would be:

Total:      0.722 + 0.833 + 0.722 = 2.277
Average:    2.277 / 3 = 0.759
Offset:     0.759 + 0.9 = 1.659
Fractional: 0.659

Rendering the continuous CA can be done by multiplying by 256 to get the corresponding greyscale colour:

Two Dimensional

Two-dimensional CAs open up a new, huge level of complexity and interest (namely the second dimension!). 2D CAs use information from their surrounding neighbours to calculate their next state.

Conway's Life

By far the most famous 2D CA is John Conway's "Game of Life", or just Life. Life came about in the late-1960s, early 1970s when Conway set about trying to simply some previous cellular automataon research by John von Neumann. Conway had wanted to find the simplest CA that supported universal computation. He decided to use two states, dead or alive, and four simple rules:

• If a live cell has less than two neighbours, it dies.
• If a live cell has more than three neighbours, it dies.
• If a dead cell has exactly three neighbours, it comes to life.
• Otherwise, all other cells remain in their original state.

As with 1D CAs, these simple rules generate incredibly complex behaviour. Indeed, it was quickly proven that Conway's Life is indeed capable of universal computation. Below is a "glider", a structure within Life that cycles between 5 states, and moves down and left each cycle.

Gliders are useful in computation because they can act as counters - imagine bits in a bit stream, where a 1 is denoted by a glider and 0 is denoted by the absense of a glider. The specifics of computation within a Life is universe is beyond the scope of this introductory essay, but here is some proof.

Here is a binary adder adding 1110 (14, shown in red) and 0011 (3, shown in blue). The result is calculated after 900 generations as 10001 (17, shown in green):

Uses of Cellular Automata

CAs have a variety of uses in the real world. Again, Flake's Computational Beauty of Nature covers this topic (and many others) in more detail, but some uses include visualization of chemical systems, gene regulation, study of multicellular organisms, study of colonies (ants, termites), flocks and herds and ecosystems/economics/society.

It is interesting to see how cellular automata can be applied at both the microscopic and macroscopic levels, simulating cellular organisms or abstracting behaviour such as that of human traffic jams, or even entire cities.

Further Reading

Besides Generation5 articles, please look at Generation5's book reviews for a variety of excellent and interesting books on artificial life and cellular automata (Artificial Life and Popular Science categories). All images of cellular automata were created with the Generation5 JDK and the excellent MCell, which is a must-download for readers wanting to play with CAs themselves. Finally, the links page provides numerous resources and pages for you to peruse.

References

Wolfram, Stephen. A New Kind of Science. Wolfram Media Inc. Champaign, IL: 2002.