Rule 90

Properties

Additivity, superposition, and decomposition

A configuration in Rule 90 can be partitioned into two subsets of cells that do not interact with each other. One of these two subsets consists of the cells in even positions at even time steps and the cells in odd positions in odd time steps. The other subset consists of the cells in even positions at odd time steps and the cells in odd positions at even time steps. Each of these two subsets can be viewed as a cellular automaton with only its half of the cells. The rule for the automaton within each of these subsets is equivalent (except for a shift by half a cell per time step) to another elementary cellular automaton, Rule 102, in which the new state of each cell is the exclusive or of its old state and its right neighbor. That is, the behavior of Rule 90 is essentially the same as the behavior of two interleaved copies of Rule 102.

Rule 90 and Rule 102 are called additive cellular automata. This means that, if two initial states are combined by computing the exclusive or of each their states, then their subsequent configurations will be combined in the same way. More generally, one can partition any configuration of Rule 90 into two subsets with disjoint nonzero cells, evolve the two subsets separately, and compute each successive configuration of the original automaton as the exclusive or of the configurations on the same time steps of the two subsets.

Deterministic solution

Rule 90 is deterministically solvable, meaning that one can express the state of a given cell after ${\displaystyle n}$ iterations starting from initial configuration ${\displaystyle x\in \{0,1{\}}^{\mathbb{Z}}}$ by an explicit formula. Let ${\displaystyle [F^n(x){]}_j}$ represent the state of cell ${\displaystyle j}$ after ${\displaystyle n}$ iterations or rule ${\displaystyle F}$, which in our case is rule 90. Initial condition is represented by ${\displaystyle x}$, so that ${\displaystyle x_i}$ is the state of cell ${\displaystyle i}$ in the initial configuration, ${\displaystyle x_i\in \{0,1\}}$. For rule 90 one can show that

${\displaystyle [F^n(x){]}_j=\sum _{i=0}^n(\genfrac{}{}{0ex}{}{n}{i})x_{2i-n+j}\mathrm{mod}2}$

Probabilistic solution

Suppose that the initial configuration is a random bi-infinite binary string ${\displaystyle x\in \{0,1{\}}^{\mathbb{Z}}}$ drawn from the Bernoulli distribution, such that probability of ${\displaystyle x_i=1}$ is equal to ${\displaystyle p\in [0,1]}$ and the probability of ${\displaystyle x_i=0}$ is ${\displaystyle 1-p}$. Then one can show that after ${\displaystyle n}$ iterations of rule 90, probabilities of occurrence of blocks ${\displaystyle 0,00,000}$, and ${\displaystyle 010}$, denoted by ${\displaystyle P_n(0),P_n(00),P_n(000)}$ and ${\displaystyle P_n(010)}$, are given by

${\displaystyle \begin{array}{cc}{P}_n(0)& =\frac{1}{2}+\frac{1}{2}{\left(1-2p\right)}^{G\left(n\right)},\\ P_n(00)& ={\left(\frac{1}{2}+\frac{1}{2}{\left(1-2p\right)}^{G\left(n\right)}\right)}^2,\\ P_n(000)& =\left(\frac{1}{4}+\frac{1}{2}{\left(1-2p\right)}^{G\left(n\right)}+\frac{1}{4}{\left(1-2p\right)}^{G\left(n+1\right)}\right)\left(\frac{1}{2}+\frac{1}{2}{\left(1-2p\right)}^{G\left(n\right)}\right),\\ P_n(010)& =\frac{1}{8}+\frac{1}{8}{\left(1-2p\right)}^{G\left(n\right)}+\frac{1}{8}{\left(1-2p\right)}^{G\left(n+1\right)}-\frac{1}{4}{\left(1-2p\right)}^{2G\left(n\right)}\\ & -\frac{1}{8}{\left(1-2p\right)}^{G\left(n+1\right)+G\left(n\right)}.\end{array}}$

where ${\displaystyle G(n)}$ is the Gould's sequence,

${\displaystyle G(n)=\sum _{k=0}^n\left((\genfrac{}{}{0ex}{}{n}{k})\mathrm{mod}2\right).}$

The remaining probabilities of blocks of length 1, 2 and 3 can be obtained using Kolmogorov consistency conditions,

${\displaystyle \begin{array}{cc}P(1)& =1-P(0),\\ P(01)& =P(0)-P(00),\\ P(10)& =P(0)-P(00),\\ P(11)& =1-2P(0)+P(00),\\ P(001)& =P(00)-P(000),\\ P(011)& =P(0)-P(00)-P(010),\\ P(100)& =P(00)-P(000),\\ P(101)& =P(0)-2P(00)+P(000),\\ P(110)& =P(0)-P(00)-P(010),\\ P(111)& =1-3P(0)+2P(00)+P(010).\end{array}}$

Stunted trees and triangular clearings

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. In particular, Gilbreath's conjecture asserts that the leftmost values in each row of this triangle are all 0 or 2. When a contiguous subsequence of values in one row of the triangle are all 0 or 2, then Rule 90 can be used to determine the corresponding subsequence in the next row. Miller (1970) explained the rule by a metaphor of tree growth in a forest, entitling his paper on the subject "Periodic forests of stunted trees". In this metaphor, a tree begins growing at each position of the initial configuration whose value is 1, and this forest of trees then grows simultaneously, to a new height above the ground at each time step. Each nonzero cell at each time step represents a position that is occupied by a growing tree branch. At each successive time step, a branch can grow into one of the two cells above it to its left and right only when there is no other branch competing for the same cell. A forest of trees growing according to these rules has exactly the same behavior as Rule 90.

From any initial configuration of Rule 90, one may form a mathematical forest, a directed acyclic graph in which every vertex has at most one outgoing edge, whose trees are the same as the trees in Miller's metaphor. The forest has a vertex for each pair (x,i) such that cell x is nonzero at time i. The vertices at time 0 have no outgoing edges; each one forms the root of a tree in the forest. For each vertex (x,i) with i nonzero, its outgoing edge goes to (x ± 1, i − 1), the unique nonzero neighbor of x in time step i − 1. 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. Such a clearing is formed when a consecutive sequence of cells becomes zero simultaneously in one time step, and then (in the tree metaphor) branches grow inwards, eventually re-covering the cells of the sequence.

For random initial conditions, the boundaries between the trees formed in this way themselves shift in a seemingly random pattern, and trees frequently die out altogether. 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. Miller used these repeating patterns to form the designs of tapestries. Some of Miller's tapestries depict physical trees; others visualize the Rule 90 automaton using abstract patterns of triangles.

Sierpiński triangle

The time-space diagram of Rule 90 is a plot in which the ith row records the configuration of the automaton at step i. When the initial state has a single nonzero cell, this diagram has the appearance of the Sierpiński triangle, a fractal formed by combining triangles into larger triangles. 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. One way to explain this structure uses the fact that, in Rule 90, each cell is the exclusive or of its two neighbors. Because this is equivalent to modulo-2 addition, this generates the modulo-2 version of Pascal's triangle. The diagram has a 1 wherever Pascal's triangle has an odd number, and a 0 wherever Pascal's triangle has an even number. This is a discrete version of the Sierpiński triangle.

The number of live cells in each row of this pattern is a power of two. In the ith row, it equals 2^k, where k is the number of nonzero digits in the binary representation of the number i. The sequence of these numbers of live cells,

1, 2, 2, 4, 2, 4, 4, 8, 2, 4, 4, 8, 4, 8, 8, 16, 2, 4, 4, 8, 4, 8, 8, 16, 4, 8, 8, 16, 8, 16, 16, 32, ... (sequence A001316 in the OEIS)

is known as Gould's sequence. The single live cell of the starting configuration is a sawtooth pattern. This means that in some time steps the numbers of live cells grow arbitrarily large while in others they return to only two live cells, infinitely often. 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.

The Sierpiński triangle also occurs in a more subtle way in the evolution of any configuration in Rule 90. At any time step i in the Rule's evolution, the state of any cell can be calculated as the exclusive or of a subset of the cells in the initial configuration. That subset has the same shape as the ith row of the Sierpiński triangle.

Replication

In the Sierpiński triangle, for any integer i, the rows numbered by multiples of 2ⁱ have nonzero cells spaced at least 2ⁱ 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 2ⁱ, then in steps that are multiples of 2ⁱ, the configuration will consist of copies of P spaced at least 2ⁱ units from start to start. This spacing is wide enough to prevent the copies from interfering with each other. The number of copies is the same as the number of nonzero cells in the corresponding row of the Sierpiński triangle. 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. In contrast, the replication in Rule 90 is trivial and automatic.

Predecessors and Gardens of Eden

In Rule 90, on an infinite one-dimensional lattice, every configuration has exactly four predecessor configurations. This is because, in a predecessor, any two consecutive cells may have any combination of states, but once those two cells' states are chosen, there is only one consistent choice for the states of the remaining cells. Therefore, there is no Garden of Eden in Rule 90, a configuration with no predecessors. The Rule 90 configuration consisting of a single nonzero cell (with all other cells zero) has no predecessors that have finitely many nonzeros. However, this configuration is not a Garden of Eden because it does have predecessors with infinitely many nonzeros.

The fact that every configuration has a predecessor may be summarized by saying that Rule 90 is surjective. The function that maps each configuration to its successor is, mathematically, a surjective function. Rule 90 is also not injective. In an injective rule, every two different configurations have different successors, but Rule 90 has pairs of configurations with the same successor. Rule 90 provides an example of a cellular automaton that is surjective but not injective. 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.

Because each configuration has only a bounded number of predecessors, the evolution of Rule 90 preserves the entropy of any configuration. In particular, if an infinite initial configuration is selected by choosing the state of each cell independently at random, with each of the two states being equally likely to be selected, then each subsequent configuration can be described by exactly the same probability distribution.

Emulation by other systems

Many other cellular automata and other computational systems are capable of emulating the behavior of Rule 90. For instance, a configuration in rule 90 may be translated into a configuration into the different elementary cellular automaton Rule 22. The translation replaces each Rule 90 cell by three consecutive Rule 22 cells. These cells are all zero if the Rule 90 cell is itself zero. A nonzero Rule 90 cell is translated into a one followed by two zeros. With this transformation, every six steps of the Rule 22 automaton simulate a single step of the Rule 90 automaton. Similar direct simulations of Rule 90 are also possible for the elementary cellular automata Rule 45 and Rule 126, for certain string rewriting systems and tag systems, and in some two-dimensional cellular automata including Wireworld. Rule 90 can also simulate itself in the same way. If each cell of a Rule 90 configuration is replaced by a pair of consecutive cells, the first containing the original cell's value and the second containing zero, then this doubled configuration has the same behavior as the original configuration at half the speed.

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. A new copy is placed to either side of the replicator pattern, as long as the space there is empty. However, if two replicators both attempt to copy themselves into the same position, then the space remains blank. In either case the replicators themselves vanish, leaving their copies to carry on the replication. A standard example of this behavior is the "bowtie pasta" pattern in the two-dimensional HighLife rule. This rule behaves in many ways like Conway's Game of Life, but such a small replicator does not exist in Life. Whenever an automaton supports replicators with the same growth pattern, one-dimensional arrays of replicators can be used to simulate Rule 90. Rule 90 (on finite rows of cells) can also be simulated by the block oscillators of the two-dimensional Life-like cellular automaton B36/S125, also called "2x2", and the behavior of Rule 90 can be used to characterize the possible periods of these oscillators.