|
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
x1 or x2 or ... or xn.
- 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
y1 or y2 or ... or ym.
The state transition rules for the GoL can be specified by the notation
Bx/Sy. Let x be the concatenation of
the numbers x1, x2, ..., xn.
Let y be the concatenation of
y1, y2, ..., ym.
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 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 29 birth rules.
The same logic applies to survival rules. There are
29 survival rules.
Each birth rule can be combined with any survival rule.
So there are:
29 29 = 218
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 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 xi in x, 8 - xi
is not in v, and vice versa.
- For each digit yj in y, 8 - yj
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 218 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.
Table 1: Counting Life-Like Celluar Automata
| Number |
Birth Rules | 29 |
Survival Rules | 29 |
Life-Like Rules | 29 29 = 262,144 |
Self-Symmetric Rules | 29 |
Non-Self-Symmetric Rules | 29(29 - 1) |
Without Symmetric Rules | 28(29 - 1) |
With Self-Symmetric Rules Added Back | 28(29 + 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