You may know about Cellular Automata. If not you may have come across them in John Conway's game of Life, but why is this whole subject so interesting? We take a look at not only what a CA is, but why it is so important.

A Programmers Guide To Theory
First Draft

There is a more recent version of this:

Now available as a paperback and ebook from Amazon.

A Programmers Guide To Theory - NP & Co-NP

Contents

1. What Is Computable?
2. Finite State Machines
3. What is a Turing Machine? 
4. Computational Complexity
5. Non-computable numbers
6. The Transfinite
7. Axiom Of Choice
8. Lambda Calculus
9. Grammar and Torture
10. Reverse Polish Notation - RPN
11. Introduction to Boolean Logic
12. Confronting The Unprovable - Gödel And All That
13. The Programmer's Guide to Fractals
14. The Programmer's Guide to Chaos*
15. Prime Numbers And Primality Testing
16. Cellular Automata - The How and Why
17. Information Theory
18. Coding Theory
19. Kolmogorov Complexity

*To be revised

The origins of CAs are difficult to pin down, but back in the early 1950s Stanislaw Ulam, a mathematician at Los Alamos, used the first digital computers to play with patterns that evolved with time. He called them “recursively defined geometry”.

The first true CAs were probably invented by Ulam’s close friend, the well-known mathematician and computer scientist Johnny Von Neumann. Ulam suggested that Von Neumann try to construct rule-based machines in an artificial universe that would help model self reproduction. He chose a chessboard universe in which each square represents a cell that can obey a set of rules. This was the first cellular automaton.

A Cellular Automaton is a very simple form of computation. If you look at the world around you what you see are things that have a position and a state. A biological cell sits at a particular spot in a clump of other cells and its state is that it is either alive or dead. You can think up other examples that are less biological, but it is this one that really drives the CA idea.

So we have something, a cell, that has a location and a state.

The key next step is to ask what is it that affects the cell's state?

In most cases you would assume that the cell's state is influenced by its local neighbourhood. What matters is what is going on where the cell is not something happening miles away.

This is the assumption of localization and it is inherent in most of classical physics. A wave, say, is described by a differential equation which relates what happens at a point to what happens in an infinitesimal region around the point.

You might want to say that the local assumption is too restrictive in that it doesn't allow for long range interactions but in the physical world long range interactions occur by an influence that moves from point-to-point. Long range interactions occur by propagation of pulses and waves which depend only on local interactions.

The final CA assumption is that of locality of influence.  A cell's state is only affected by the local conditions. In most cases we reduce this even further to say that a cell's state is only influenced by its current state and the states of neighboring cells.

The idea is that you start of with an initial colony of cells, each one with an initial state, and then you allow the colony to develop. This is usually done using discrete time steps - you can run CAs in continuous time, but this is more difficult.

At time t you have the positions and states of all the cells; you then apply a rule that gives the state of each cell according to its current state and the state of neighbouring cells. At time t+1 the cells all change their state according to the same rule.

Clearly to define a CA you have to specify the possible states, the initial arrangement of cells and the update rule.

So what do you hope this sort of computation might be good for?

You can think of CAs as the digital version of classical differential equations which are used to describe so much of physics. However CAs aren't as easy to analyze as you might expect. The nature of the rule used in a typical CA makes it very difficult to predict what will happen given any initial condition.

For example, you might like to ask if a given set of cells will oscillate, die away or grow without bound - you might like to ask, but finding an answer is much more difficult. CAs are intriguing because they are unpredictable and mostly unfathomable.

CAs are examples of how local rules can result in globally organized behaviour - or at least what looks like globally organized behaviour.