|
|
| Line 1: |
Line 1: |
| {{Short description|Elementary cellular automaton}}
| |
| [[File:R090 rand 0.png|thumb|upright=1.35|Time-space diagram of Rule 90 with random initial conditions. Each row of pixels is a configuration of the automaton; time progresses vertically from top to bottom.]]
| |
| In the [[mathematics|mathematical]] study of [[cellular automaton|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.<ref name="w83">{{citation|first=Stephen|last=Wolfram|authorlink=Stephen Wolfram|title=Statistical mechanics of cellular automata|journal=Reviews of Modern Physics|issue=3|volume=55|pages=601–644|year=1983|doi=10.1103/RevModPhys.55.601|url=http://www.stephenwolfram.com/publications/articles/ca/83-statistical/|bibcode=1983RvMP...55..601W}}.</ref> {{harvtxt|Martin|Odlyzko|Wolfram|1984}} call it "the simplest non-trivial cellular automaton",<ref name="mow84">{{citation|first1=Olivier|last1=Martin|first2=Andrew M.|last2=Odlyzko|author2-link=Andrew Odlyzko|first3=Stephen|last3=Wolfram|author3-link=Stephen Wolfram|title=Algebraic properties of cellular automata|year=1984|journal=Communications in Mathematical Physics|pages=219–258|volume=93|issue=2|doi=10.1007/BF01223745|url=http://www.stephenwolfram.com/publications/articles/ca/84-properties/|bibcode = 1984CMaPh..93..219M }}.</ref> and it is described extensively in [[Stephen Wolfram]]'s 2002 book ''[[A New Kind of Science]]''.<ref>{{citation|first=Stephen|last=Wolfram|authorlink=Stephen Wolfram|title= A New Kind of Science|url=https://www.wolframscience.com/nks/|year=2002|publisher=Wolfram Media}}. The book's index lists over 50 distinct subtopics for Rule 90.</ref>
| |
|
| |
|
| 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 (cellular automaton)|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 [[power of two|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 [[Tapestry|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 (cellular automaton)|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). 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).
| |
|
| |
| ==Description==
| |
| ===Rules===
| |
| [[File:Rule 90 gate array.svg|thumb|In Rule 90, each cell's value is computed as the exclusive or of the two neighboring values in the previous time step.]]
| |
| 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.<ref name="w83"/>
| |
|
| |
| 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:<ref name="w83"/>
| |
| <center>
| |
| {| class="wikitable" style="text-align:center"
| |
| |-
| |
| ! current pattern !! 111 !! 110 !! 101 !! 100 !! 011 !! 010 !! 001 !! 000
| |
| |-
| |
| ! new state for center cell
| |
| | 0 || 1 || 0 || 1 || 1 || 0 || 1 || 0
| |
| |}
| |
| </center>
| |
|
| |
| ===Naming===
| |
| The name of Rule 90 comes from [[Stephen Wolfram]]'s [[Wolfram code|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]]: 01011010<sub>2</sub> = 90<sub>10</sub>.<ref name="w83"/> Rule 90 has also been called the '''Sierpiński automaton''', due to the characteristic [[Sierpiński triangle]] shape it generates,<ref name="cns04"/> and the '''Martin–Odlyzko–Wolfram cellular automaton''' after the early research of {{harvs|first1=Olivier|last1=Martin|first2=Andrew M.|last2=Odlyzko|author2-link=Andrew Odlyzko|first3=Stephen|last3=Wolfram|author3-link=Stephen Wolfram|year=1984|txt}} on this automaton.<ref>{{citation|first1=Michał|last1=Misiurewicz|first2=John G.|last2=Stevens|first3=Diana M.|last3=Thomas|author3-link= Diana Thomas |title=Iterations of linear maps over finite fields|journal=Linear Algebra and Its Applications|volume=413|issue=1|year=2006|pages=218–234|doi=10.1016/j.laa.2005.09.002|doi-access=free}}.</ref>
| |
|
| |
| ==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.<ref>{{citation|first=Harold V.|last=McIntosh|url=http://delta.cs.cinvestav.mx/~mcintosh/comun/wandl/global.pdf|year=1993|title=Ancestors: Commentaries on "The Global Dynamics of Cellular Automata" by Andrew Wuensche and Mike Lesser (Addison-Wesley, 1992)|publisher=Instituto de Ciencias, Universidad Autónoma de Puebla}}.</ref>
| |
| 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.<ref>{{citation
| |
| | last = Kawaharada | first = Akane
| |
| | doi = 10.14492/hokmj/1416837570
| |
| | issue = 3
| |
| | journal = Hokkaido Mathematical Journal
| |
| | mr = 3282639
| |
| | pages = 361–383
| |
| | title = Ulam's cellular automaton and Rule 150
| |
| | volume = 43
| |
| | year = 2014| doi-access = free
| |
| }}: "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."</ref>
| |
|
| |
| 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.<ref name="mow84"/>
| |
|
| |
| ===Stunted trees and triangular clearings===
| |
| [[File:Rule 90 trees.svg|thumb|upright=1.35|A forest of stunted trees. This is a time-space diagram, but with time running upwards, not downwards. Interestingly, the fifth tree did not sprout in both directions despite being able to.]]
| |
| 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 number]]s. 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. {{harvtxt|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.<ref name="m70">{{citation|first=J. C. P.|last=Miller|authorlink=J. C. P. Miller|title=Periodic forests of stunted trees|journal=Philosophical Transactions of the Royal Society of London|series=Series A, Mathematical and Physical Sciences|volume=266|issue=1172|year=1970|pages=63–111|jstor=73779|doi=10.1098/rsta.1970.0003|bibcode = 1970RSPTA.266...63M }}.</ref>
| |
|
| |
| From any initial configuration of Rule 90, one may form a [[Tree (graph theory)|mathematical forest]], a [[directed acyclic graph]] in which every [[Vertex (graph theory)|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 {{math|(''x'',''i'')}} such that cell {{math|''x''}} is nonzero at time {{math|''i''}}. The vertices at time 0 have no outgoing edges; each one forms the root of a tree in the forest. For each vertex {{math|(''x'',''i'')}} with {{math|''i''}} nonzero, its outgoing edge goes to {{math|(''x'' ± 1, ''i'' − 1)}}, the unique nonzero neighbor of {{math|''x''}} in time step {{math|''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.<ref name="m70"/>
| |
|
| |
| 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 register]]s 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.<ref name="m70"/><ref>{{citation|first=H. G.|last=ApSimon|title=Periodic forests whose largest clearings are of size 3|journal=Philosophical Transactions of the Royal Society of London|series=Series A, Mathematical and Physical Sciences|volume=266|issue=1172|year=1970|pages=113–121|jstor=73780|doi=10.1098/rsta.1970.0004|bibcode=1970RSPTA.266..113A}}; {{citation|first=H. G.|last=ApSimon|title=Periodic forests whose largest clearings are of size ''n'' ≥ 4|journal=Philosophical Transactions of the Royal Society of London|series=Series A, Mathematical and Physical Sciences|volume=266|issue=1538|year=1970|pages=399–404|jstor=73780|doi=10.1098/rspa.1970.0185 |bibcode=1970RSPSA.319..399A}}. A similar analysis of periodic configurations in Rule 90 also appears in {{harvtxt|Wolfram|2002}}, p. 954.</ref>
| |
| Miller used these repeating patterns to form the designs of [[tapestry|tapestries]]. Some of Miller's tapestries depict physical trees; others visualize the Rule 90 automaton using abstract patterns of triangles.<ref name="m70"/>
| |
|
| |
| ===Sierpiński triangle===
| |
| [[File:R090 pulse wide.png|thumb|upright=1.5|[[Sierpiński triangle]] generated by Rule 90]]
| |
| The time-space diagram of Rule 90 is a plot in which the {{math|''i''}}th row records the configuration of the automaton at step {{math|''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 [[triangle]]s 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 [[modular arithmetic|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.<ref name="w83"/><ref>{{harvtxt|Wolfram|2002}}, pp. 25–26, 270–271, 870.</ref>
| |
|
| |
| The number of live cells in each row of this pattern is a [[power of two]]. In the {{math|''i''}}th row, it equals {{math|2<sup>''k''</sup>}}, where {{math|''k''}} is the number of nonzero digits in the [[binary number|binary representation]] of the number {{math|''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, ... {{OEIS|A001316}}
| |
| is known as [[Gould's sequence]].
| |
| The single live cell of the starting configuration is a [[Sawtooth (cellular automaton)|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.<ref name="cns04">{{citation|first1=Jens Christian|last1=Claussen|first2=Jan|last2=Nagler|first3=Heinz Georg|last3=Schuster|title=Sierpinski signal generates 1/''f''<sup> ''α''</sup> spectra|journal=Physical Review E|volume=70|year=2004|issue=3|page=032101|doi=10.1103/PhysRevE.70.032101|pmid=15524560|arxiv=cond-mat/0308277|bibcode = 2004PhRvE..70c2101C }}.</ref>
| |
|
| |
| The Sierpiński triangle also occurs in a more subtle way in the evolution of any configuration in Rule 90. At any time step {{math|''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 {{math|''i''}}th row of the Sierpiński triangle.<ref>{{citation|first1=B. K.|last1=Kar|first2=A.|last2=Gupta|first3=P. Pal|last3=Chaudhuri|title=On explicit expressions in additive cellular automata theory|journal=Information Sciences|volume=72|issue=1–2|pages=83–103|year=1993|doi=10.1016/0020-0255(93)90030-P}}.</ref>
| |
|
| |
| ===Replication===
| |
| In the Sierpiński triangle, for any integer {{math|''i''}}, the rows numbered by multiples of {{math|2<sup>''i''</sup>}} have nonzero cells spaced at least {{math|2<sup>''i''</sup>}} units apart. Therefore, because of the additive property of Rule 90, if an initial configuration consists of a finite pattern {{math|''P''}} of nonzero cells with width less than {{math|2<sup>''i''</sup>}}, then in steps that are multiples of {{math|2<sup>''i''</sup>}}, the configuration will consist of copies of {{math|''P''}} spaced at least {{math|2<sup>''i''</sup>}} 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 (cellular automaton)|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.<ref name="replicator">{{citation|first=Abraham|last=Waksman|title=A model of replication|journal=[[Journal of the ACM]]|volume=16|issue=1|year=1969|pages=178–188|doi=10.1145/321495.321509}}; {{citation|first1=Serafino|last1=Amoroso|first2=Gerald|last2=Cooper|title=Tessellation structures for reproduction of arbitrary patterns|journal=Journal of Computer and System Sciences|volume=5|issue=5|pages=455–464|year=1971|doi=10.1016/S0022-0000(71)80009-0|doi-access=free}}. {{harvtxt|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.</ref>
| |
|
| |
| ===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 (cellular automaton)|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.<ref name="skyum"/>
| |
|
| |
| The fact that every configuration has a predecessor may be summarized by saying that Rule 90 is [[surjective function|surjective]]. The function that maps each configuration to its successor is, mathematically, a surjective function. Rule 90 is also not [[injective function|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 (cellular automaton)|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.<ref name="skyum">{{citation|first=Sven|last=Skyum|title=Confusion in the Garden of Eden|journal=Proceedings of the American Mathematical Society|volume=50|issue=1|pages=332–336|year=1975|doi=10.1090/S0002-9939-1975-0386350-1|doi-access=free}}</ref><ref>{{citation|journal=Complex Systems|volume=5|year=1991|pages=19–30|title=De Bruijn Graphs and Linear Cellular Automata|first=Klaus|last=Sutner|url=http://www.complex-systems.com/pdf/05-1-3.pdf}}. {{harvtxt|Wolfram|2002}}, pp. 959–960. {{harvtxt|Martin|Odlyzko|Wolfram|1984}} provide a similar analysis of the predecessors of the same rule for finite sets of cells with periodic boundary conditions.</ref>
| |
|
| |
| 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.<ref name="mow84"/>
| |
|
| |
| ==Emulation by other systems==
| |
| [[File:Highlife replicator.png|thumb|The bowtie pasta replicator in HighLife, one-dimensional arrays of which can be used to emulate Rule 90]]
| |
| 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 system]]s and [[tag system]]s, 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.<ref>{{harvtxt|Wolfram|2002}}, pp. 269–270, 666–667, 701–702, 1117.</ref>
| |
|
| |
| 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 (cellular automaton)|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.<ref>{{citation|contribution=Recipe for the week of July 1–7: Replicating Skeeters|first=David|last=Griffeath|url=http://psoup.math.wisc.edu/archive/recipe75.html|year=1996|title=The Primordial Soup Kitchen}}.</ref> Rule 90 (on finite rows of cells) can also be simulated by the block [[Oscillator (cellular automaton)|oscillators]] of the two-dimensional [[{{Not a typo|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.<ref>{{citation|first=Nathaniel|last=Johnston|contribution=The B36/S125 "2x2" {{Not a typo|Life-like}} cellular automaton|pages=99–114|title=Game of Life Cellular Automata|editor-first=Andrew|editor-last=Adamatzky|editor-link=Andrew Adamatzky|publisher=Springer-Verlag|year=2010|arxiv=1203.1644|bibcode = 2010golc.book...99J |doi = 10.1007/978-1-84996-217-9_7 }}.</ref>
| |
|
| |
| == See also ==
| |
| *Other elementary cellular automata: [[Rule 30]], [[Rule 110]], and [[Rule 184]]
| |
|
| |
| == References ==
| |
| {{reflist|colwidth=30em}}
| |
|
| |
| == External links ==
| |
| *{{MathWorld |title = Rule 90 |urlname = Rule90|mode=cs2}}
| |
| *[http://atlas.wolfram.com/01/01/90/ Rule 90 in Wolfram's atlas of cellular automata]
| |
|
| |
| {{DEFAULTSORT:Rule 030}}
| |
| [[Category:Cellular automaton rules]]
| |
