A CA That Finds Edges

As an example of a CA that does something useful, consider the consider a rectangular grid of cells where each one has a state of black or white and the initial setup:

The rule that each of the cells 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 cell horizontally or vertically adjacent.

What do you think the result of this simple rule is going to be when all of the cells 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 cells 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.

John Conway's Life

Our example is very simple and while it might be impressive it is uncharacteristically easy to understand for a CA. The best known of all CAs is Conway's Life and this seems just as simple but it has taken a long time to work out even simple things about how it behaves and we are still making discoveries.

This was devised in 1970 by John Horton Conway, a Cambridge mathematician, and made a public appearance via Martin Gardner’s column in Scientific American (Oct 1970 and Feb 1971).

The rules of Life are very simple. The universe is a rectangular grid with each grid square representing a cell, which can be either alive or dead (on or off if you want a less emotive description).

Each cell clearly has eight neighbours and what happens at each generation depends on how many neighbours N it has:

N           Next generation
2           No change
3           Alive or On
0,1,4-8     Dead or off

Notice that the rule is very simple. If you imagine that you are a cell sitting in the middle of a huge rectangle of other cells it is very easy for you to find out what to do. You simply count how many of your eight neighbours are alive and if the result is 3 you set your state to “on” (irrespective of what it is currently). If it is exactly 2 then you don’t change your state and for any other value you set your state to Off.

You can see that Life is an entirely local process in the sense that no cell has any idea of what it is going on globally. You might also think that Life is really going to be very boring and that large-scale structures are unlikely to happen – but in this case you would be wrong.

For example, just try and predict what will happen to a line of cells – one cell, then two, then three and so on.

A single cell dies at once.

Two cells also die at the first step, however three cells do something remarkable and give the first hint that there is a lot going on here. Three cells arranged in a horizontal line flip to three cells in a vertical line at the next generation and then back again to three in a horizontal row. We have an oscillator!

Four cells form a solid block and then a block with a hole in it that is stable and unchanging.

Five cells go through a sequence of changes to produce a set of four 3-cell oscillators.

Six cells go through a sequence of interesting shapes and then vanish.

By now you are probably getting the idea.

Life isn’t predictable!