Cellular Automata

If we want to build a theory based on programs we need to examine the way programs really work.

We need to look at the simplest sorts of programs that might account for the behavior of the more fundamental things of the Universe. There are a number of possible ways we could go about this – Turing machines, grammars, recursive logic and so on but the one that is used in “A New Kind of Science” and central to its explanation is the Cellular Automata, CAs.

Not only are CAs interesting models of program behavior they are also a lot of fun. What you might not realise by their being brought into the public eye by Wolfram’s book, they were invented in the 1940s by Ulam and Von Neumann. They were interested in finding computer-like models of self-reproducing machines that had the characteristics of living organisms.

A CA is basically a rule that a set of agents can apply locally. A full mathematical definition is possible and while such a model would be more complete it would also be more difficult to follow.

The agents, or whatever you want to call them, are usually arranged in some sort of pattern – often a grid – and they can usually only see the agent that they are close to and each agent can usually be in one of a number of states – often either zero or one.

Each agent is equipped with a rule, usually the same rule, and this tells them how to change their state according to their current state and the state of nearby agents. Usually the changes occur altogether on the tick of a clock that all of the agents can hear.

You might just recognise the description of a well-known computer game called Life, devised by John Conway, in this slightly abstract formulation of a CA; and indeed Conway’s Life is an example of a much-studied CA.

If you would like to see how CAs might be useful consider a grid of agents which are initially set to either black or white as shown:

The rule that each of the agents are going to obey at the next clock tick is the following:

If you are black and have a white neighbor then stay black otherwise turn white.

Where in this case a neighbor is defined to be any agent horizontally or vertically adjacent.

What do you think the result of this simple rule is going to be when all of the agents obey it?
What might surprise you is that this rule only leaves the outline of the original shape in black:

In other words, the rule succeeded in picking out the outline of the shape. Notice that nothing but local information was used by any of the agents and yet it succeeded in extracting something that we might think of as global, i.e. the outline.

It’s the same sort of phenomenon as the displays of pictures and patterns that happen at sporting events when members of the crowd are given cards to hold up at specified times.

A global pattern can result from the application of a local rule.

Putting this another way, it should be clear that a simple rule can lead to complex behavior. The rules for Life for example are very simple but we are still studying the behaviors that it can exhibit.