Simple Cellular Automaton

A cellular automaton is a mathematical object that consists of (usually) an infinite regular grid of cells, each of which may be in a finite number of states and a set of transition rules, according to which the cells change their states simultaneously in discrete time steps. The same rules apply to each and every cell. Most commonly the number of states is 2. In one of the states the cells are often said to be alive, in the other to be dead. Sometimes, the entire set of cells is referred to as a generation. An application of transition rules to one generation produces another generation and then is applied again, and so on.

The applet below implements a simple cellular automaton that may obey one of 5 rules that are represented graphically in the diagram. The rules apply to the marked cell. The latter transitions according to the number of live cells among those present (the marked cell itself and the neighbors that appear in the diagram.)

(1)

For rule 2n, the marked cell is alive in the next generation if at least two of the three cells in the diagram are alive presently. For the same purpose rules 3n and 3d require at least three cells, rules 4n and 4d require at least four live cells. Reduction in the number of required live cells may result in stable structures - immortal barren populations that reproduce themselves with every application of a transition rule. For example, if in rule 4n the presence of three live cells ensures inclusion of the marked cell into the next generation, then four live cells that form a 2×2 square remain alive indefinitely. However, the way the above rules have been set up, for any of them, any finite population will die out in a finite number of steps.

In fact, a problem with rule 2n has been included in the 1973 All-Union Soviet Olympiad [Savchev, pp. 149-151]. One solution by a Russian tenth-grader A. Gomilko that I'll present shortly got a special prize for elegance.

The problem was twofold. First, it was required to prove that, for rule 2n, any initial population will eventually die out. The second part of the problem stipulated that the extinction of life will take place in a number of steps not exceeding the number of live cells in the initial population.

(The applet may be useful to acquire intuition as to the change in population from generation to generation. You can create a random population and also modify each of the cells by clicking on it.)

If you are reading this, your browser is not set to run Java applets. Try IE11 or Safari and declare the site https://www.cut-the-knot.org as trusted in the Java setup.

What if applet does not run?

Discussion

References

S. Savchev, T. Andreescu, Mathematical Miniatures, MAA, 2003

First let's see why whichever rule (2n - 4d) is used to produce a new generation, any initial population will, with time, die out. All the rules at hand have a certain property of monotonicity to introduce which let's agree to denote the number of live cells in a generation G as G_L. A generation engendered by an application of a transition rule to a generation G is a function of G, say, f(G). The monotonicity of f is formally expressed in the following manner:

(2)	If G_L ⊂ H_L then f(G)_L ⊂ f(H)_L,

which merely says that a live cell would be alive if the process started with a bigger live population.

Except for 3d, all rules (1) possess another property. Since the number of live cells in a generation is assumed to be finite, the live cells in a generation can be include into a grid rectangle R. Then, for all rules (1), but 3d,

(3)	If G_L ⊂ R then f(G)_L ⊂ R,

which simply says that no member of a population of live cells contained in a grid rectangle ever crosses outside that rectangle.

The two properties (2) and (3) suggest a way to prove the first part of the problem. For a rectangular live population R, a pattern of extinction is easily discerned by experimentation. Any (finite) live population can be included into a rectangular one, where it stays indefinitely, by (3), and expires at least as fast as the latter, by (2).

Now, A. Gomilko's solution for the second part of the problem and rule 2n. The proof is by mathematical induction.

Clearly, a lone live cell disappears in 1 step. Assume that a population of k live cells, k < n, expires in no more than k steps, and consider a generation G with exactly n live cells. Let R be the minimal (grid) rectangle that contains all live population of the given generation. Along with R, we shall consider two sub-rectangles: one R_b is obtained by omitting the bottom row of cells, the other R_l by omitting the leftmost column of R. Since R is the minimal rectangle that contains G_L, the dropped row and column are bound to contain some live cells. Therefore, the number of life cells in either R_b or R_l is less than n. Application of the rule 2n to the rectangles R_b and R_l is not affected by the omitted cells. It follows by induction hypothesis that the populations of both rectangles, R_b and R_l, will die out in not more than n-1 steps. So, in n-1 steps, the only survivor may be located in the lower left corner of R; but this will be eliminated in 1 additional step.

For the 2n rule, we can give another proof. This time we concentrate on the distribution of live cells on the NW-SE diagonals. The specifics of the pattern of expiration for the rule 2n is best discerned by considering a live population filling up a rectangle. First the NE corner is emptied. Next, the two cells to the left and below that corner die. These second-step cells form a (2-cell) NW-SE diagonal. Next to it NW-SE diagonal dies on the third step, and so on. Thus, an application of the 2n rule causes any diagonal next to a diagonal void of live cells to perish. Looking at the process a little differently, each contiguous group of live cells situated on a NW-SE diagonal can be thought to be enclosed by a square whose diagonal it is. The diagonal moves in the perpendicular direction (NE-SW) staying inside this square until it meets its (timely) end in the SW corner. The number of steps it takes is exactly the length of the diagonal. Another important observation is that the diagonals move independently, without affecting each other. What may be affected by their relative locations is whether their demise takes place in parallel or sequentially. (E.g., a column of live cells may be considered as a set of 1-element diagonals that die sequentially.)

To sum up, a contiguous NW-SE diagonal of, say, s live cells, dies in s steps. If the n live cells are situated on t such diagonals, so that

s₁ + s₂ + ... + s_t = n,

the most it may take for all n cells to die, which happens when the diagonals die sequentially, is exactly

s₁ + s₂ + ... + s_t = n.

It takes fewer steps if some of the expiration processes proceed in parallel.

Note, there are indeed n-cell populations that expire in exactly n steps. The diagram below gives one such example for n = 9.

Let's now compare the effect of different rules on the same population. In order to survive under the rule 3n a cell needs more live neighbors than with the rule 2n; and even more so for rule 4n. Thus, in obvious notations,

(4)	f_4n(G)_L ⊂ f_3n(G)_L ⊂ f_2n(G)_L,

With rules 3n and 4n, the population shrinks even faster than under rule 2n. Under rule 3d, the bounding rectangle does not remain fixed, but rather moves leftwards. Its left edge stops moving after reaching the situation in which it contains a single live cell. On the other hand, the right edge moves rightwards inexorably emptying the rectangle in a finite number of steps. How many does it take? Under rule 3d, any population in a bounding rectangle with k cell rows and m columns, will die out in at most [k/2] + m generations. But it may take that long only if there are at least 2 live cells in each column, i.e. when n > 2m. We must also have n > k, which would imply n > [k/2] + m. But these estimates are exaggerated. The populations in non touching bounding rectangles live and die independently and in parallel. Thus if n = n₁ + ... + n_t, where n_i is the number of live cells in a rectangle of size k_i×m_i, such that no two rectangles have live neighbors, the population will shrink as slow as the slowest of those rectangles, in which n_i > [k_i/2] + m_i. But clearly n > n_i, for any I.

(To tell the truth, the previous paragraph offers an argument of the sort I like least. In a visually simple situation it appears unnecessarily long-winded. I'd be happy to learn of a more elegant reasoning.)

Cellular Automaton

Life-like Automaton With Definable Rules
Sierpinski's Gasket and Dihedral Symmetry
Simple Cellular Automaton
The Game of Life

71945612