Rule 90
In the mathematical study of cellular automata, 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 their 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 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. When Rule 90 is started from a random initial configuration, its configuration remains random at each time step. 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.
Some of the earliest studies of Rule 90 were made in connection with an unsolved problem in number theory, Gilbreath's conjecture, on the differences of consecutive prime numbers. This rule is also connected to number theory in a different way, via Gould's sequence. This sequence counts the number of nonzero cells in each time step after starting Rule 90 with a single live cell. Its values are powers of two, with exponents equal to the number of nonzero digits in the binary representation of the step number. Other applications of Rule 90 have included the design of tapestries.
Every configuration of Rule 90 has exactly four predecessors, other configurations that form the given configuration after a single step. 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 provides an example of a cellular automaton that is surjective (each configuration has a predecessor) but not injective (it has sets of more than one configuration with the same successor), showing that the converse of the Garden of Eden theorem is not true.
Description
Rules
Rule 90 is an elementary cellular automaton. That means that it 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, and then progresses through other configurations in a sequence of discrete time steps. At each step, all cells are updated simultaneously. A pre-specified rule determines the new value of each cell as a function of its 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,[4] and the Martin–Odlyzko–Wolfram cellular automaton after the early research of Olivier Martin, Andrew M. Odlyzko, and Stephen Wolfram (1984) on this automaton.[5]
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.[6] 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.[7]
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.[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, 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.[8]
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.[8]
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] 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.[8]
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 the same diagram. 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.[1][10]
The number of live cells in each row of this pattern is a power of two. In the ith row, it equals 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 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 exponentially growing sawtooth wave shape that can be used to recognize physical processes that behave similarly to Rule 90.[4]
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.[11]
Replication
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. 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.[12]
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.[13]
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.[13][14]
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.[2]
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.[15]
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. 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.[16] 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.[17]
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 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 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.
- ↑ Kawaharada, Akane (2014), "Ulam's cellular automaton and Rule 150", Hokkaido Mathematical Journal, 43 (3): 361–383, doi:10.14492/hokmj/1416837570, MR 3282639: "Except for trivial CAs the other four linear elementary CAs, Rule 60, Rule 90, Rule 102 and Rule 150, are either essentially equivalent to Rule 90 or Rule 150."
- 1 2 3 4 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.
- ↑ 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 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.