Cellular Automata

Cellular automata were first devised by Ulam and von Neumann at Los Alamos during the Manhattan project in the early 1940s. Somewhat later, Ulam in particular wrote an influential paper entitled “On some mathematical problems connected with patterns of growth of figure” in the Proceedings of Symposia in Applied Mathematics, 14: 215-224, 1962. I was hoping to find the original article and working note which I once had when I lived in Buffalo, NY but I haven’t found it yet – in time I will get it and link it. Maybe Mike Woldenberg had it as I remember the original Los Alamos paper. To progress though, a rather good summary of the development of CA is given by Cosma Shalizi in his CA Notebook which has many good references.

Essentially a CA works by assuming some regular lattice of cells – in this case we will consider them to be 2-dimensional like a topographic map. Each cell has a state or series of states that it can take on and the neighbouring cells determine what this state might be. The neighbours are defined usually as the nearest neighbours and the Moore neighbourhood consists of the eight cells around a cell in question if the lattice is square.

A rather neat way of illustrating a CA was first devised as a game by John Conway in 1970 which he called the Game of Life. This consists of randomly planting a series of cells which are alive on a lattice and determining how they grow and survive dependent on those cells around them. If a cell is alive, then it stays alive if 2 or 3 cells in its neighbouhood are alive (survival). It dies if there is less than 2 cells (isolation) or more than 3 (overcrowding, congestion) in its neighbourhood. A cell comes alive if there are exactly 3 cells in its neighbourhood already alive (reproduction). That is all there is to it – The interesting feature of this CA is that cells survive, life persists, with the rules being necessary and sufficient for life. Here is an example that you can play around with.

Click on the lattice above to launch the web page that lets you interact with the Game of Life.