Rule 90
Rule 90 is an elementary cellular automaton based on the exclusive or function. It consists of a one-dimensional array of cells, each of which can hold either a 0 or a 1 value; in each time step all values are simultaneously replaced by the exclusive or of the two neighboring values.[1] Martin, Odlyzko & Wolfram (1984) call it "the simplest non-trivial cellular automaton",[2] and it is described extensively in Stephen Wolfram's 2002 book A New Kind of Science.[3] When started from a random initial configuration, its configuration remains random at each time step;[2] however, any configuration with only finitely many nonzero cells becomes a replicator that eventually fills all of the cells with copies of itself.[4]
Rules
An elementary cellular automaton consists of a one-dimensional array of cells, each of which holds a single binary value, either 0 or 1. An assignment of values to all of the cells is called a configuration. The automaton is given an initial configuration, after which its configuration repeatedly changes in a sequence of discrete time steps. At each step, all cells are updated simultaneously, according to a pre-specified rule which determines the new value as a function of each cell's previous value and of the values in its two neighboring cells. All cells obey the same rule, which may be given either as a formula or as a rule table that specifies the new value for each possible combination of neighboring values.[1]
In the case of Rule 90, each cell's new value is the exclusive or of the two neighboring values. Equivalently, the next state of this particular automaton is governed by the following rule table:[1]
| current pattern | 111 | 110 | 101 | 100 | 011 | 010 | 001 | 000 |
|---|---|---|---|---|---|---|---|---|
| new state for center cell | 0 | 1 | 0 | 1 | 1 | 0 | 1 | 0 |
Naming
The name of Rule 90 comes from Stephen Wolfram's binary-decimal notation for one-dimensional cellular automaton rules. To calculate the notation for the rule, concatenate the new states in the rule table into a single binary number, and convert the number into decimal: 010110102 = 9010.[1] Rule 90 has also been called the Sierpiński automaton, due to the characteristic Sierpiński triangle shape it generates,[5] and the Martin–Odlyzko–Wolfram cellular automaton after the early research of Olivier Martin, Andrew M. Odlyzko, and Stephen Wolfram (1984) on this automaton.[6]
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.[7] It 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 additive cellular automata: 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. Thus, more generally, one can partition any configuration into two subsets with disjoint nonzero cells, evolve the two subsets separately, and compute the behavior of the original automaton by superposing configurations derived from the two subsets.[2]
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, most values are either 0 or 2, and Rule 90 describes the pattern of nonzeros that arises once all other values have been eliminated. Miller (1970) explained the rule by a metaphor of tree growth in a forest: each time step represents a height above the ground (with the initial configuration representing the ground level) and each nonzero cell represents a growing tree branch. At each successive level, a branch can grow into one of the cells only when there is no other branch competing for the same cell.[8]
From any initial configuration of Rule 90, one may form a mathematical forest, a directed acyclic graph in which every node has at most one outgoing edge, by creating a node for each pair (x,i) such that cell x is nonzero at time i, and by connecting each such node (with i > 0) to 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. 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.[8][9]
Additionally, Miller used these regular patterns to form the designs of tapestries depicting physical trees as well as abstract patterns of triangles.[8]
Sierpiński triangle
The time-space diagram of Rule 90 (a plot in which the ith row records the configuration of the automaton at step i) has the appearance of the Sierpiński triangle fractal when responding to an initial state with a single nonzero cell. Rules 18, 22, 26, 82, 146, 154, 210 and 218 generate the same sequence. 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, which is a discrete version of the Sierpiński triangle.[1][10]
The number of live cells in the ith row of this pattern is 2k, 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 OEIS)
known as Gould's sequence or Dress's sequence, has a characteristic exponentially growing sawtooth shape that can be used to recognize physical processes that behave similarly to Rule 90.[5]
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, each cell has a state that is 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.[11]
Replication
In the Sierpiński triangle, for any integer i, the rows with positions that are multiples of 2i consist of some number of nonzero cells spaced 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 2i 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. However, unlike the replicators in more complex rules such as the Von Neumann universal constructor, Codd's cellular automaton, or Langton's loops, the replication in Rule 90 is trivial and automatic, rather than requiring each replicator pattern to carry and copy a sequence of instructions for building itself.[4]
Predecessors and Gardens of Eden
In Rule 90, on an infinite one-dimensional lattice, every configuration has exactly four predecessor configurations: in the 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, this rule provides an example of a cellular automaton that is surjective (each configuration has a predecessor, so there is no Garden of Eden) but not injective (unlike injective rules, Rule 90 has pairs of configurations with the same successor). 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.[12][13]
Because each state has 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.[2]
The Rule 90 configuration consisting of a single nonzero cell (with all other cells zero) has no predecessor that have finitely many nonzeros, but it is not a Garden of Eden because it has predecessors with infinitely many nonzeros.[12]
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 by replacing each Rule 90 cell by three consecutive Rule 22 cells that are either all zero (if the Rule 90 cell is itself zero) or a one followed by two zeros (if the Rule 90 cell is a one). 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 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, in which the first cell in the pair contains the original cell's value, and the second contains a zero, then this doubled configuration has the same behavior as the original configuration at half the speed.[14]
Various other cellular automata are known to support replicators, patterns that make copies of themselves, with 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, but if two replicators both attempt to copy themselves into the same position, then the space remains blank, and 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, a rule that except for the behavior of this pattern behaves in many ways like Conway's Game of Life. Whenever an automaton supports replicators with this growth pattern, one-dimensional arrays of replicators can be used to simulate Rule 90.[15] 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.[16]
See also
References
- 1 2 3 4 5 Wolfram, Stephen (1983), "Statistical mechanics of cellular automata", Reviews of Modern Physics 55 (3): 601–644, Bibcode:1983RvMP...55..601W, doi:10.1103/RevModPhys.55.601.
- 1 2 3 4 Martin, Olivier; Odlyzko, Andrew M.; Wolfram, Stephen (1984), "Algebraic properties of cellular automata", Communications in Mathematical Physics 93 (2): 219–258, Bibcode:1984CMaPh..93..219M, doi:10.1007/BF01223745.
- ↑ Wolfram, Stephen (2002), A New Kind of Science, Wolfram Media. The book's index lists over 50 distinct subtopics for Rule 90.
- 1 2 Waksman, Abraham (1969), "A model of replication", Journal of the ACM 16 (1): 178–188, doi:10.1145/321495.321509; Amoroso, Serafino; Cooper, Gerald (1971), "Tessellation structures for reproduction of arbitrary patterns", Journal of Computer and System Sciences 5 (5): 455–464, doi:10.1016/S0022-0000(71)80009-0. Wolfram (1983) (Fig.33 and surrounding text) also mentions the same property, and as well as citing Waksman, Amoroso, and Cooper he credits its observation to unpublished work by Edward Fredkin in 1981.
- 1 2 Claussen, Jens Christian; Nagler, Jan; Schuster, Heinz Georg (2004), "Sierpinski signal generates 1∕f α spectra", Physical Review E 70: 032101, arXiv:cond-mat/0308277, Bibcode:2004PhRvE..70c2101C, doi:10.1103/PhysRevE.70.032101.
- ↑ Misiurewicz, Michał; Stevens, John G.; Thomas, Diana M. (2006), "Iterations of linear maps over finite fields", Linear Algebra and its Applications 413 (1): 218–234, doi:10.1016/j.laa.2005.09.002.
- ↑ McIntosh, Harold V. (1993), Ancestors: Commentaries on "The Global Dynamics of Cellular Automata" by Andrew Wuensche and Mike Lesser (Addison-Wesley, 1992) (PDF), Instituto de Ciencias, Universidad Autónoma de Puebla.
- 1 2 3 Miller, J. C. P. (1970), "Periodic forests of stunted trees", Philosophical Transactions of the Royal Society of London, Series A, Mathematical and Physical Sciences 266 (1172): 63–111, Bibcode:1970RSPTA.266...63M, doi:10.1098/rsta.1970.0003, JSTOR 73779.
- ↑ ApSimon, H. G. (1970), "Periodic forests whose largest clearings are of size 3", Philosophical Transactions of the Royal Society of London, Series A, Mathematical and Physical Sciences 266 (1172): 113–121, doi:10.1098/rsta.1970.0004, JSTOR 73780; ApSimon, H. G. (1970), "Periodic forests whose largest clearings are of size n ≥ 4", Philosophical Transactions of the Royal Society of London, Series A, Mathematical and Physical Sciences 266 (1538): 399–404, doi:10.1098/rspa.1970.0185, JSTOR 73780. A similar analysis of periodic configurations in Rule 90 also appears in Wolfram (2002), p. 954.
- ↑ Wolfram (2002), pp. 25–26, 270–271, 870.
- ↑ Kar, B. K.; Gupta, A.; Chaudhuri, P. Pal (1993), "On explicit expressions in additive cellular automata theory", Information Sciences 72 (1–2): 83–103, doi:10.1016/0020-0255(93)90030-P.
- 1 2 Skyum, Sven (1975), "Confusion in the Garden of Eden", Proceedings of the American Mathematical Society 50 (1): 332–336, doi:10.1090/S0002-9939-1975-0386350-1
- ↑ Sutner, Klaus (1991), "De Bruijn Graphs and Linear Cellular Automata" (PDF), Complex Systems 5: 19–30. Wolfram (2002), pp. 959–960. Martin, Odlyzko & Wolfram (1984) provide a similar analysis of the predecessors of the same rule for finite sets of cells with periodic boundary conditions.
- ↑ Wolfram (2002), pp. 269–270, 666–667, 701–702, 1117.
- ↑ Griffeath, David (1996), "Recipe for the week of July 1–7: Replicating Skeeters", The Primordial Soup Kitchen.
- ↑ Johnston, Nathaniel (2010), "The B36/S125 "2x2" Life-like cellular automaton", in Adamatzky, Andrew, Game of Life Cellular Automata, Springer-Verlag, pp. 99–114, arXiv:1203.1644, Bibcode:2010golc.book...99J, doi:10.1007/978-1-84996-217-9_7.