Figure 1: Random Patterns in Life and Flip Life |

**1.0 Introduction**

I have
occasionally
posted
about
automata.
A discussion with a colleague about Stephen Wolfram's
*A New Kind of Science*
reminded me that I had started this post some time last year.

This post has nothing to do with economics, albeit it does illustrate emergent behavior. And I have figures that are an eye test. I am subjectively original. But I assume somebody else has done this - that I am not objectively original.

This post is an exercise in combinatorics. There are 131,328 life-like Celluar Automata (CA), up to symmetry.

**2.0 Conway's Game of Life**

John Conway will probably ever be most famous for the Game of Life (GoL). I wish I understood monstrous moonshine.

The GoL is "played", if you can call it that, on an infinite plane divided into equally sized squares. The plane looks something like a chess board, extended forever. See the left side of Figure 1, above. Every square, at any moment in time, is in one of two states: alive or dead. Time is discrete. The rules of the game specify the state of each square at any moment in time, given the configuration at the previous instant.

The state of a square does not depend solely on its previous state. It also depends on the states of its neighbors. Two types of neighborhoods have been defined for a CA with a grid of square cells. The Von Neumann neighbors of a cell are the four cells above it, below it, and to the left and right. The Moore neighborhood (Figure 2) consists of the Von Neumann neighbors and the four cells diagonally adjacent to a given cell.

Figure 2: Moore Neighborhood of a Dead Cell |

The GoL is defined for Moore neighborhoods. State transition rules can be defined in terms of two cases:

**Dead cells:**By default, a dead cell stays dead. If a cell was dead at the previous moment, it becomes (re)born at the next instant if the number of live cells in its Moore neighborhood at the previous moment was*x*_{1}or*x*_{2}or ... or*x*_{n}.**Alive Cells:**By default, a live cell becomes dead. If a cell was alive at the previous moment, it remains alive if the number of live cells in its Moore neighborhood at the previous moment was*y*_{1}or*y*_{2}or ... or*y*_{m}.

The state transition rules for the GoL can be specified by the notation
B*x*/S*y*. Let *x* be the concatenation of
the numbers *x*_{1}, *x*_{2}, ..., *x*_{n}.
Let *y* be the concatenation of
*y*_{1}, *y*_{2}, ..., *y*_{m}.
The GoL is B3/S23. In other words, if exactly three of the neighbors of a dead
cell are alive, it becomes alive for the next time step. If exactly two or
or three of the neighbors of a live cell are alive, it remains alive at the next
time step. Otherwise a dead cell remains dead, and a live cell becomes dead.

The GoL is an example of recreational mathematics. Starting with random patterns, one can predict, roughly, the distributions of certain patterns when the CA settles down, in some sense. On the other hand, the specific patterns that emerge can only be found by iterating through the GoL, step by step. And one can engineer certain patterns.

**3.0 Life-Like Celluar Automata**

For the purposes of this post, a *life-like CA* is a CA defined with:

- A two dimensional grid with square cells and discrete time
- Two states for each cell
- State transition rules specified for Moore neighborhoods
- State transition rules that can be specified by the B
*x*/S*y*notation.

How many life-like CA are there? This is the question that this post attempts to answer.

The Moore neighborhood of cell contains eight cells. Thus, for each of the
digits 0, 1, 2, 3, 4, 5, 6, 7, and 8, they can appear in B*x*.
For each digit, one has two choices. Either it appears in the birth
rule or it does not. Thus, there are 2^{9} birth rules.

The same logic applies to survival rules. There are
2^{9} survival rules.

Each birth rule can be combined with any survival rule. So there are:

2^{9}2^{9}= 2^{18}

life-like CA. But this number is too large. I am double counting, in some sense.

**4.0 Reversing Figure and Ground**

Figure 1 shows, side by side, grids from the GoL and from a CA called Flip Life. Flip Life is specified as B0123478/S01234678. Figure 3 shows a window from a computer program. In the window on the left, the rules for the GoL are specified. The window on the right is used to specify Flip Life.

Figure 3: Rules for Life and Flip Life |

Flip Life basically renames the states in the GoL. Cells that are called dead in the GoL are said to be alive in Flip Life. And cells that are alive in the GoL are dead in Flip Life. In counting the number of life-like CA, one should not count Flip Life separately from the GoL. In some sense, they are the same CA.

More generally,
suppose B*x*/S*y* specifies a life-like CA, and let B*u*/S*v* be the
life-like CA in which figure and ground are reversed.

- For each digit
*x*_{i}in*x*, 8 -*x*_{i}is not in*v*, and vice versa. - For each digit
*y*_{j}in*y*, 8 -*y*_{j}is not in*u*, and vice versa.

So for any life-like CA, one can find another symmetrical CA in which dead cells become alive and vice versa.

**5.0 Self Symmetrical CAs**

One cannot just divide 2^{18} by two to find the number of life-like CA, up
to symmetry. Some rules define CA that are the same CA, when one reverses figure
and ground. As an example, Figure 4 presents a screen snapshot for the CA called
Day and Night, specified by the rule B1/S7.

Figure 4: Day and Night: An Example of a Self-Symmetrical Cellular Automaton |

Given rules for births, one can figure out what the rules must be for survival for the CA to be self-symmetrical. Thus, there are as many self-symmetrical life-like CAs as there are rules for births.

**6.0 Combinatorics**

I bring all of the above together in this section. Table 1 shows a tabulation of the number of life-like CAs, up to symmetry.

Number | |

Birth Rules | 2^{9} |

Survival Rules | 2^{9} |

Life-Like Rules | 2^{9} 2^{9} = 262,144 |

Self-Symmetric Rules | 2^{9} |

Non-Self-Symmetric Rules | 2^{9}(2^{9} - 1) |

Without Symmetric Rules | 2^{8}(2^{9} - 1) |

With Self-Symmetric Rules Added Back | 2^{8}(2^{9} + 1) = 131,328 |

**7.0 Conclusion**

How many of these 131,328 life-like CA are interesting? Answering this question requires some definition of what makes a CA interesting. It also requires some means of determining if some CA is in the set so defined. Some CAs are clearly not interesting. For example, consider a CA in which all cells eventually die off, leaving an empty grid. Or consider a CA in which, starting with a random grid, the grid remains random for all time, with no defined patterns ever forming. Somewhat more interesting would be a CA in which patterns grow like a crystal, repeating and duplicating. But perhaps an interesting definition of an interesting CA would be one that can simulate a Turing machine and thus may compute any computable function. The GoT happens to be Turing complete.

**Acknowledgements:** I started with version 1.5 of Edwin Martin's implementation, in Java, of John Conway's Game of Life. I have modified this implementation in several ways.

**References**

- David Eppstein (2010). Growth and Decay in Life-Like Celluar Automata

## No comments:

Post a Comment