If you grew up, like I did, writing code for fun, then there is good chance that you will have implemented some form of Conway’s Life on one of computers you owned (and maybe a Mandelbrot renderer, and a Sieve of Eratosthenes to calculate Prime numbers too … ?)

If you are not familiar with Life, it’s a classic simulation, invented by John Conway in 1970. It’s a type of program given the fancy name of a Cellular Automaton, and it’s a crude approximation of life on a rectangular gridded Petri Dish.

Cells (squares) are either occupied or empty. Cells states are determined by following a very small collection of simple rules (based on the state of their immediate neighbors).

The cells (colonies), can change with each iteration. Sometimes they die out totally. Sometimes they continue growing and expanding forever (proven), and sometimes they reach a steady state (either static, or oscillating between a series of fixed states with a common time-base).

There are many awesome sites on the web dedicated to Life, and some viciously optimized implementations that allow you to experiment with gigantic layouts in times I could only dream about when I wrote my first version (in 6502 assembly). Go Google some and play, but for more fun, if you haven’t already, go implement a Life engine in your favorite programing language (I’ve even read about people implementing it in SQL!)

The geometry of some patterns causes them to move and translate across the grid. Two of the simplest are shown to the right.

The Glider (the smallest possible stable moving ship), moves diagonally. The LWSS translates purely in one coordinate direction.

Streams of spaceships can be arranged to collide and intersect with other elements to give different results depending on the number of spaceships present. It's possible to arrange elements to make fundamental logic gates such as AND, OR, and NOT, and a finite state machine. Simply put, this simple cellular automaton is can be configured into a computer! And, as it is Turing complete, given a massively large grid and timebase, there is no reason it could not perform the same calculations as the computer you are reading this web page on!

The rules for Langton's Ant are even simpler than Conway's Life. An ant sits on a particular square of the grid. If the square it is currently sitting on is set, it turns right (a quarter turn) then moves one space forward (unsetting the state of the cell as it leaves). If the square it is currently sitting on is unset, the it turns left and moves forward one space (setting the state of the cell as it leaves).

That's it! The rules are that simple.

On every move the state of the square the ant was occupying is toggled (set/unset). Every time-tick it turns 90° and moves forward one space, and it's only the state of the current square that determines if it turns left or right.

In the animation on the left, black is used to identify cells that are 'set' and white for 'unset'.

The red arrow shows the direction the ant is facing when it is in each cell (not the direction it's going to move).

Something interesting happens. Initially the patterns formed are very simple, and often go through cycles of symmetry. However, after a few hundred steps things start to turn chaotic and the image starts to look random. Finally just before 11,000 steps, structure appears and an emergent pathway appears out of the chaos. This pathway is formed as a stable repeating pattern of base approx 100 operations that translates across and down and continues in this form forever.