Cellular automata are simple discrete simulations which turn up unusually frequently in the real world. The concept was thought up in the 1940's by Stanislaw Ulam and John von Neumann but was popularized much later after computers became widespread. These days cellular automata appear as Ising models in physics as well as naturally in the patterns in some seashells, they can also be used simply to make some elegant patterns.
A cellular automata consists of two simple parts
- A grid of coloured cells
- An update function where each cell acquires a new colour which depends only on the cell itself along with its neighbours.
Let's look at a simple example. See the grid below, it consists of 30 cells in a row each coloured either white or red. We are going to apply a simple update rule called majority. For each cell we will look at the colour of itself and its 2 immediate neighbours. Then its new colour will be whichever colour is the most common. For example if the grid looked like red white red, the middle cell would become red and there are 2 reds and only 1 white among itself and it 2 neighbours.
The step button advances the automata one step, updating every cell as described above. The randomize button gives each cell a random colour. Observe that in this case, after a couple of steps the automata freezes. Is there anything you notice about frozen states? How could you work out if you've reached the frozen stage without pressing the step button?
Another possible simple update rule would be to simply take on the colour of the cell to your right. What do you think this would look like? Click the button labelled Change Update Rule to find out.
In general, these sort of automata are usually displayed on a two dimensional grid where each step corresponds to moving down one level and the colours are usually white and black. Using the above automata as examples we would get the following figures:
So far these automata have not produced anything particularly interesting but we at least can generate some nice looking patterns with our left moving rule. Things will get much more interesting though when we start to play around with less human update rules. To make things a little more mathematical, as opposed to thinking of our cells as having one of 2 colours, we can think of assigning to each cell either a 0 or a 1. With this in mind, our previous 2 update rules can be expressed as:
| Update Rule | 111 | 110 | 101 | 100 | 011 | 010 | 001 | 000 |
|---|---|---|---|---|---|---|---|---|
| Majority | 1 | 1 | 1 | 0 | 1 | 0 | 0 | 0 |
| Left Mover | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 |
Reading the rows left to right, the majority update rule corresponds to the string 11101000 which in binary translates to 232. Similarly the left mover update rule gives 101010102 = 17010. Hence every possible update rule of this form will correspond to an integer between 0 and 255 (111111112). This gives us an easy way to generate new update rules, all we need to do is pick a number between 0 and 255 and then convert it to binary. For example lets look at the update rule 30. As 30 = 16 + 8 + 4 + 2, we see 3010 = 000111102 and so the update rule will be:
| Update Rule | 111 | 110 | 101 | 100 | 011 | 010 | 001 | 000 |
|---|---|---|---|---|---|---|---|---|
| 30 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 |
Let's have a look at what this gives us:
As you can see we are getting a much more intricate pattern. Let's see what happens if we shrink down the size of all our cells so we can get a better look at the larger structures.
Somewhat surprisingly we end up with an image that looks somewhat but not completely random and has a collection of interesting features such as the appearance of triangles. This is known as emergent behaviour as it was not at all clear from looking at the update rule that this would appear and this is a common feature of cellular automata.
This concept of emergence turns up throughout science in places where simple building blocks lead to highly complicated systems. For example, going from particle physics describing the interactions of elementary particles to trying to explain how molecules work in chemistry or cells in biology.
I'll leave you with a little gadget to let you try out some update rules by yourself. You can also pick what colours you want to display. It's currently set on rule 73, which gives something that looks a lot like a Persian rug. Some other rules I've found which give interesting patterns are 82, 86, 93, 107, 110, and 120 and there are many more so please try some numbers out more yourself and let me know if you find any patterns you particularly like.