Life is a complex system that arises from a simple rule.

What is more, Life is just one example of a range of similar cellular automata – each a simple collection of rules that invariably lead to complex behavior.

In general a CA is a universe of cells each of which can be in one of a number of states with the addition of a set of rules that depend only on the cells in the immediate neighborhood of the cell.

Given that these CAs are small artificial universes then you can see that we aren’t doing very well at explaining them. In our own universe we speculate that everything might well be based on some simple rule that generates all of the complexity, and hence we go in search of grand unified theories or a theory of everything. If we can’t find a theory of everything in situations when we know the rules then things look bleak indeed!

A partial solution to the problem is to simplify. The range of possible rules that you can invent for a CA of the sort that Life typifies is just too great. If, however, you start with just a one-dimensional universe then the possibilities are far fewer.This idea was first tried out by Stephen Wolfram, the man who invented the maths program Mathematica, in the early 1980s.

You might think that one-dimensional CAs are so trivial that they wouldn’t be worth study but again you would be wrong. There is enough complexity in a one-dimensional CA to keep us thinking and there are still unsolved problems in the field. See: Cellular Automata - The How and Why.

What one dimensional automata showed is that we can at least classify simple CAs but Life is another matter!

If my comments about understanding the way simplicity gives rise to complexity don’t strike you as particularly important or practical it is worth saying that CAs are being used to model such things as the growth of forests and other biological systems.

You can even attempt to model the behavior of physical systems using them – snowflakes for example. It also seems very likely that the way that the genetic code works, biological cell creation and morphogenesis (how the shape of organisms develops under the control of genes) all seem likely to be CAs. They are also important foundations for new subjects such as the study of artificial life.

Artificial life is more or less where it all started with Von Neumann and his search for a self-reproducing machine. What seemed to be an almost ridiculous theory is looking like turning out to be hard fact with the new science of nano-machines. What could be more natural than to build a nanobot that can reproduce itself and CAs give us the theory of how it can be done.

When you start thinking about the generality that CAs embody, that is the idea that local rules can produce global structures, then you can begin to see that their application is surprisingly wide. In fact there are even people who believe that the entire universe is just a CA!

The real attraction of CAs is that they are simple to understand but have a depth of behavior that keeps you interested.

Programs

If you want to try out Life then download Golly. This is a general purpose Life simulator and comes with a range of sample patterns. If you want to explore Life seriously then this is the place to start. It also can implement rules for other CAs.

If you want to find out more about CAs in general then why not download the Cellular Automata Laboratory from:

It doesn't run directly under Windows 7 and 8 any more but it isn't difficult to get it working.

You will also find lots of interesting documents at the same site. The CA Lab is very general in the sense you can load a range of rule sets and starting configurations including the rules of Life but if you study the documentation you will be able to go well beyond Life … to the universe and everything..

The Cellular Automata Laboratory lets you experiment with a wide range of CAs

Further Reading

There are a great many books on CAs and artificial life in general. If you want a general introduction without too much technical detail then try: Artificial Life: A Report from the Frontier Where Computers Meet Biology by Steven Levy. A more technical but still readable account of the same topic Introduction to Artificial Life by Christoph Adami is good. For a complete overview of CAs and how they might produce a new theory of everything you have to read :A New Kind of Science by Stephen Wolfram, even if you are certain not to agree with everything it says.

Details of these books can be found in the sidebar above.

Performing a computation sounds simple like a simple enough task and it is easy to suppose that everything is computable. In fact there are a range of different types of non-computability that we need [ ... ]

We often state that program is just a list of instructions, but this does not do justice to the complexity of this apparently simple idea. A the idea of a program exists outside of any particular prog [ ... ]