Cellular Automata - The How and Why
Written by Mike James   
Article Index
Cellular Automata - The How and Why
Life and beyond
One-dimensional CAs

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!

In fact Life is so difficult to understand that even simple questions proved very difficult to answer. For example, are there any patterns which grow without end? In 1969 Conway discovered an interesting little pattern of five cells which he called a glider.

glider

Five cells that walk across the Life universe

What made this interesting was that a glider walks its way across the Life universe and behaves like a basic particle that can be used to build other shapes.

However the real breakthrough came in 1970 when, in order to win a $50 prize, Bill Gosper discovered the glider gun.

This complicated arrangement of cells fired a new glider every 30 generations. At last it was proved that there were patterns which grew without limit because the gun added five cells every 30 generations.

More important, however, was the fact that with a glider gun you could now begin to build machines in Life space!

The streams of gliders could be used as if they were electric currents and thus logic gates and memory could be built. Soon a complete Life computer was constructed proving that the simple rule, involving only local behaviour of each cell, gave rise to a something as complicated as a digital computer. In other words, it was equivalent to a universal Turing machine that could compute anything that could be computed.

 

gun

A glider gun – you can see two gliders moving off down and to the right

After the glider gun, all sorts of interesting shapes were discovered – oscillators, movers, emitters and so on.

The most important thing to notice is that even today Life is an experimental subject, very little if anything has been proved theoretically. 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 behaviour.

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 neighbourhood 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!

There are lots of 2D CAs and indeed Life is just an example of a set of CAs called "Totalistic". In a totalistic CA the state of a cell is an integer which only depends on the sum of the states of its neighbours and possibly its current state.



 
 

   
RSS feed of all content
I Programmer - full contents
Copyright © 2014 i-programmer.info. All Rights Reserved.
Joomla! is Free Software released under the GNU/GPL License.