Fun with cellular automata: Conway's Game of Life

A cellular automaton (CA) is an incredibly simple thing. But when you put a bunch of them together, you can produce incredibly fascinating results. The individual machines are trivial, but when you put them together in large numbers, you can do just about anything. To me, this is an amazing thing: incredibly complexity and even beauty can emerge from the simplest of mathematical systems.

Basically, CAs are grids of lots and lots of trivial machines called cells. Each cell can be in one of a small number of colors (sometimes also called states). The CA runs in steps, where every cell runs its program once each step; and in each step, it can look at what the colors of its neighbors were in the previous step, and use that to decide what color it should turn. In fact, that's really the only computation it can do: choose a new color, based on what color it was last step, and what colors its neighbors were in the previous step.

The most famous CA is called Conway's Game of Life; we'll take a look at that first. In the Game of Life, the cells are arranged in a rectangular grid. Each cell has 8 neighbors: north, northeast, east, southeast, south, southwest, west, and northwest. At any given time, each cell is either black (alive) or white (dead). For example, here's a single cell with its neighbors; the cell is black, but all of its neighbors are white:



In Life, the rules for how a cell picks its color are:

1. Statis rule: If a cell is white, and it has less than three black neighbors, it stays white.
   
2. Birth rule: If a cell is white, and it has three black neighbors, it turns black.
   
3. Survival rule:If a cell is black, and it has either two or three black neighbors, it stays black.
   
4. Overcrowding rule: If a cell is black, and it has more than three black neighbors, it turns white (dies)
   
5. Loneliness rule: If a cell is black, and it has either zero or one black neighbors, it turns white (dies).
   

So what can you do with this? Life is a very neat playground for figuring out how to construct interesting patterns. The simplest stable pattern is a black square:



In the square, each cell in the square has three live neighbors, and so they stay alive; the cells outside of the square never have more than two live neighbors, and so they never become alive.

A more interesting stable pattern is a flicker-cross - it's a pattern which alternates between two states. The flicker cross is a row of three black cells. When the cells are a vertical row, the center cell has two live neighbors, and so it stays alive; the top and bottom cells each have only one neighbor, and so they die. But the cells horizontally next to the center cell have three neighbors, and so they're born; so it switches to a horizontal row of three. Here's an image of the two states of a flicker cross, with the number of live neighbors marked in each square.



One last pattern for today, my favorite of the simple ones. This is called a glider. The glider is a semi-stable pattern. It doesn't create a stable pattern in one place, but it creates a pattern that moves accross the grid. It goes through four states, and winds up one cell north and one cell west of where it started:




How much can you do with something as simple as the game of life? You can draw a pattern which is a universal turing machine - so this seemingly trivial little thing is capable of doing any task which can be done by any computing device.

There's a nifty applet online to let you watch the Life CA in action, and play with lots of different patterns.