Rule 90
[3] When started from a single live cell, Rule 90 has a time-space diagram in the form of a Sierpiński triangle.
The behavior of any other configuration can be explained as a superposition of copies of this pattern, combined using the exclusive or function.
Any configuration with only finitely many nonzero cells becomes a replicator that eventually fills the array with copies of itself.
Its time-space diagram forms many triangular "windows" of different sizes, patterns that form when a consecutive row of cells becomes simultaneously zero and then cells with value 1 gradually move into this row from both ends.
Therefore, in contrast to many other cellular automata such as Conway's Game of Life, Rule 90 has no Garden of Eden, a configuration with no predecessors.
It follows from the Garden of Eden theorem that Rule 90 is locally injective (all configurations with the same successor vary at an infinite number of cells).
That means that it consists of a one-dimensional array of cells, each of which holds a single binary value, either 0 or 1.
[2] The Rule 90 automaton (in its equivalent form on one of the two independent subsets of alternating cells) was investigated in the early 1970s, in an attempt to gain additional insight into Gilbreath's conjecture on the differences of consecutive prime numbers.
In the triangle of numbers generated from the primes by repeatedly applying the forward difference operator, it appears that most values are either 0 or 2.
Each nonzero cell at each time step represents a position that is occupied by a growing tree branch.
Miller observed that these forests develop triangular "clearings", regions of the time-space diagram with no nonzero cells bounded by a flat bottom edge and diagonal sides.
But by means of the theory of shift registers he and others were able to find initial conditions in which the trees all remain alive forever, the pattern of growth repeats periodically, and all of the clearings can be guaranteed to remain bounded in size.
Some of Miller's tapestries depict physical trees; others visualize the Rule 90 automaton using abstract patterns of triangles.
[8] The time-space diagram of Rule 90 is a plot in which the ith row records the configuration of the automaton at step i.
Rules 18, 22, 26, 82, 146, 154, 210 and 218 also generate Sierpinski triangles from a single cell, however not all of these are created completely identically.
The growth rate of this pattern has a characteristic growing sawtooth wave shape that can be used to recognize physical processes that behave similarly to Rule 90.
[11] In the Sierpiński triangle, for any integer i, the rows numbered by multiples of 2i have nonzero cells spaced at least 2i units apart.
Therefore, because of the additive property of Rule 90, if an initial configuration consists of a finite pattern P of nonzero cells with width less than 2i, then in steps that are multiples of 2i, the configuration will consist of copies of P spaced at least 2i units from start to start.
Thus, in this rule, every pattern is a replicator: it generates multiple copies of itself that spread out across the configuration, eventually filling the whole array.
Other rules including the Von Neumann universal constructor, Codd's cellular automaton, and Langton's loops also have replicators that work by carrying and copying a sequence of instructions for building themselves.
The Garden of Eden theorem of Moore and Myhill implies that every injective cellular automaton must be surjective, but this example shows that the converse is not true.
[15] Various other cellular automata are known to support replicators, patterns that make copies of themselves, and most share the same behavior as in the tree growth model for Rule 90.
