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.)
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.)
|What if applet does not run?|
- S. Savchev, T. Andreescu, Mathematical Miniatures, MAA, 2003
Copyright © 1996-2017 Alexander Bogomolny
First let's see why whichever rule
|(2)||If GL ⊂ HL 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 GL ⊂ 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,
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
s1 + s2 + ... + st = n,
the most it may take for all n cells to die, which happens when the diagonals die sequentially, is exactly
s1 + s2 + ... + st = 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
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)||f4n(G)L ⊂ f3n(G)L ⊂ f2n(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
(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.)
- Life-like Automaton With Definable Rules
- Sierpinski's Gasket and Dihedral Symmetry
- Simple Cellular Automaton
- The Game of Life
Copyright © 1996-2017 Alexander Bogomolny