Click to download my OpenGL 1-dimensional cellular automaton.

Ever since my early days of graphics programming I've always been fascinated with fractals and cellular automata. Probably the two most well-known examples are the Mandelbrot set in the case of fractals and The Game of Life in the case of cellular automata. However, there is an even more simple example that will present both self-similar fractal patterns and the chaotic behaviour seen in the game of life. I am of course talking about 1-dimensional cellular automata.

There is no point in me repeating Wolfram's work on cellular automata, although I will just give a quick description - A 1-dimensional cellular automata is basically a grid of squares (or pixels), the left -> right direction is a normal dimension, and the up -> down direction represents time, so each row of pixels represents one generation of the cellular automaton. Each pixel can either be "alive" or "dead", represented by the colours black and white. Each generation is calculated a pixel at a time by taking the values of the three nearest pixels of the previous generation and applying a rule - because 3 pixels are taken into account and each of those pixels can either be alive or dead, that gives us a total of 256 possible rules. Each rule is numbered and can also be represented in binary - in my program you can see both of these representations of the rule numbers.

A lot of those 256 rules don't do anything interesting at all, but some of them do some really very interesting things. For me, this is what fills in the gap between a random mixture of chemicals and Darwinian evolution.

Let's start by looking at rule 22:

What you see above is called a Sierpiński Triangle - it is one of the most simple self-similar sets. Self-similarity is a fractal property which simply means the image is the same when seen at many different scales. In the image above you see a few hundred generations of the automata, but you could continue on to infinity generating larger and larger (and more and more complex) triangles. Remember this is generated by simply starting at the top and working down one pixel, one line at a time following a simple rule to determine whether each pixel in the next generation is "alive" or "dead".

However, while the Sierpiński Triangle is a pretty fractal, it's not really that surprising - it's not particularly complex. Although it's interesting that you can generate it from such simple rules, that in itself was never new to me. I learned to draw pretty pictures using a programming language called Logo at school from a very early age, 8 or 9 or so - it was never a surprise to me that loops can be used to draw some pretty amazing pictures. However, the next thing I'm going to show you really does come as a surprise:

Notice how this is exactly the same rule number, rule 22, the only thing that's changed is the initial conditions - the 'seed'. By simply changing the seed, the same rule that produced our simple ordered Sierpiński Triangle above is now producing this highly complex and chaotic behaviour. In one simple rule, this program shows how both order and chaos can arise from the same simple algorithm. Let's just look at one other interesting rule:

Here we see that even with a single pixel seed, rule 110 generates some seriously chaotic behaviour. What's particularly interesting is that along the edge of the triangle you see regular behaviour which sends a regular 'streamer' towards the center. However, these streamers interract with the chaotic stream of random triangles that meander downwards apparently randomly. I've actually increased the number of generations here and zoomed out a bit so you can see quite how random the patterns really are. Actually, they continue like this endlessly, apparently random indefinitely (as far as we know, forever). This is, in effect, a pseudorandom number generator.

What this demonstration shows is 'chaos' - a concept that was really quite revolutionary at the time, in fact it went counter to established science. Complex behaviour can arise spontaniously from such a simple set of rules, in this case a very simple set, almost the simplest it is possible to have. What's more interesting is that the same rules that can produce complex, chaotic behaviour, can also produce highly ordered patterned behaviour. In effect, order and chaos are two sides of the same coin.

For me, this, in combination with the theory of evolution is all I need to provide convincing evidence that the laws of nature do not require a designer - in effect, these are the first steps towards a scientific proof that god does not exist. Chaos theory shows how complex behaviour can arise from simple starting conditions and rules, the theory of evolution shows how these complex behaviours can become progressively more complex and ultimately reach what we now know as intelligent behaviour. No designer is required. Of course, this doesn't prove that no designer exists, simply that none is necessary.

I'll finish this little essay with another version of rule 110, same rule, different starting conditions:

A 1-dimensional cellular automaton is so easy to implement and so beautiful that it has become the first program I always write when testing a new graphics API. I've written this code in pretty much every language I know, using pretty much every graphics API. It is, in effect, my "Hello World" program for graphics systems. Click on the link below to download my version in C using the OpenGL API - this is a very basic implementation using NeHe's OpenGL basecode. The algorithm is actually very inefficient, it re-generates the entire image each time a frame is rendered, so if you increase the number of generations too far the framerate decreases drastically. However, the code is so simple that the executable is only 72k in size and requires no external dependencies.

Click to download my OpenGL 1-dimensional cellular automaton.