Reversing Figure And Ground In Life-Like Celluar Automata

by
Robert Vienneau
My articles My siteMy booksMy videos
Follow on:

Figure 1: Random Patterns in Life and Flip Life

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.

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₁ or x₂ 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₁ or y₂ or ... or y_m.

The state transition rules for the GoL can be specified by the notation Bx/Sy. Let x be the concatenation of the numbers x₁, x₂, ..., x_n. Let y be the concatenation of y₁, y₂, ..., 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.

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 Bx/Sy 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 Bx. For each digit, one has two choices. Either it appears in the birth rule or it does not. Thus, there are 2⁹ birth rules.

The same logic applies to survival rules. There are 2⁹ survival rules.

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

2⁹ 2⁹ = 2¹⁸

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

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 Bx/Sy specifies a life-like CA, and let Bu/Sv 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.

One cannot just divide 2¹⁸ 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.

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.

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.

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