Example of a Two-Dimensional Cellular Automaton, the "Game of Life"

Introduction to 2D Cellular Automata and the "Game of Life"

Whereas a single row, or array, of cells constitutes the state of a 1-D cellular automaton at a certain moment or “tick of the clock”, a series of rows, or array of arrays, constitutes a 2-D CA. So if a 2-D CA consists of 5 rows of 10 cells in each row, and each cell can exist in a state 0 or state 1, the overall state of the CA at a certain moment might look like this:


Just as with a 1D CA, we can display the 0’s and 1’s as colored pixels, which will be one of two colors. But whereas we can watch the evolution of a 1-D CA universe on a single screen, with each row presenting the state of the universe at the next tick of the clock,  each tick of the clock of a 2-D CA requires a screen of its own, to be replaced by a new screen at the next click the CA evolves.   

We can treat each row and column as continuous so that the left-most cell of each row is the left neighbor of the right-most cell, and the top-most cell in each column is the lower neighbot of the bottom-most cell. It is interesting to consider what form this takes if considered three dimensionally. You might instinctively think this would make a sphere, but in fact it forms a toroid, a donut.

In addition to deciding whether the cells at the left/right and top/bottom edges connect, we must also consider which cells are neighbors of any cell. We could decide that the cells left and right, and above and below are the neighbors (four neighbors in a neighborhood of five cells), or we might also include the cells that touch a cell only at the corner (making a total of eight neighbors in a neighborhood of nine cells).

2D CA, Four Neighbors
2D CA, Four Neighbors
2D CA, Eight Neighbors
2D CA, Eight Neighbors

And, whereas a 1-D CA with a 3-cell neighborhood (2 neighbors) might have any of just 256 different rules (or universes), a 2D CA with a 5-cell neightborhood (four neighbors) can have 2 to the power of 2 to the power of 5 rules, which is 2 the power of  32, which is 4,294,967,296 different possible rules, and a 2D CA with a 9-cell neighborhood (eight neigbors) can have 2 to the power of 2 to the power of 9, which is 2 the power of 512, which is 1.340781e+154, a number so large it is unimaginable!  That’s a LOT of different universes! And remember we’re talking about universes that each contain just a grid of cells each of which can only have 2 different states, and universal rules that defined by just a small neighborhood of cells. It is very humbling. 

Clearly we cannot define all of these  possible rules, so what does this mean when it comes to defining the rules for a 2-D CA universe? It means we must take a statistical approach and explore this universe by experiment rather than exhaustively. For example we might make a rule that states: “if exactly 5  neighbors are 1’s or exactly 8 neighbors are 0’s then the cell evolves to state 1, otherwise the cell evolves to state 0. We can try out different rules in this way and see what happens, and gradually get a feel for what rules might be more or less interesting. 

The Game of Life, developed by  John Conway in 1970 is a 2-D CA of 2-state cells (0 or 1), with a neighborhood of 5 (that is, four neighbors) that displays some interesting, even fascinating, behaviors.  The rules for this particular CA are as follows:

Any live cell (1) with fewer than two live neighbours dies (0), as if caused by underpopulation.
Any live cell (1) with two or three live neighbours lives on (1) to the next generation.
Any live cell (1) with more than three live neighbours dies (0), as if by overpopulation.
Any dead cell (0) with exactly three live neighbours becomes a live cell (1), as if by reproduction.
Of course we must be careful when using words like “underpopulation” and “reproduction”. These are just metaphorical terms used to consider a specific set of rules. But such language can help us to investigate interesting rule sets. It’s important to recognize that each universe that is defined by a specific rule set actually does exhibit very specific behaviors, each universe is different. Initially random states of cells evolve into certain patterns, sometimes reducing to a single state (easy to visualize as “dying”), sometimes to 2 or more oscillatings states, and so. What’s more, particular groupings of cells can develop identifiable behaviors (entities), such as an entity that “migrates” through the universe (passing from cell to cell like a virus or a message).  It is easy to make comparisons, with a virus, or a signal, or a mandala, or a living entity. These local behaviors will also be interacting with others as the CA evolves, leading to new patterns and entities which can be fascinating to watch. The potential for these behaviors is implicit in the rules of a specific universe, and a mathematician will be interested in whether such behaviors can be deducible without actually running and observing the CA. 
John Conway’s Game of Life offers an excellent example of a 2D CA. I’ve developed a version that allows you to view a number of different initial conditions and observe how they evolve over time. The Game of Life CA exhibits a number of behaviors that have been widely noted. Some cell groupings die out, some settle into unchanging patterns, some oscillate between two patterns, while others will “move” across the screen (these have been termed gliders). I have included a number of initial condition to play with, including one hat consists of just a single glider so you can identify this more easily and look for its occurrence in the more random initializations as they evolve. 
Running a 2D, you feel like an observer gazing into in an unknown world. In the language of chaos theory, you can think of the emergent behaviors that are inherent to a particular CA universe as attractors, inevitable destinations of initial cell states that reflect the inherent properties of the rules of the universe. 
And remember that here we are considering the Game of Life, which is just one universe of the millions of possible 2D 2-state 4 neighbor CAs. Of course you can code CA’s with a greater range of possible cell states, different definitions of neighborhoods, and different dimensions (3D, 4D, 5D, ..). Truly a universe of universes!