Rule 184

<h2 id="definition">Definition</h2>
A state of the Rule 184 automaton consists of a one-dimensional <a href="/facts/Array_data_structure/BKGvF8AM">array</a> of cells, each containing a <a href="/facts/Bit/S972NSaD">binary value</a> (0 or 1). In each step of its evolution, the Rule 184 automaton applies the following rule to each of the cells in the array, simultaneously for all cells, to determine the new state of the cell:<a class="footnote-ref" id="fnref:3" href="#fn:3">3</a>

<table><tbody><tr><th>current pattern</th><td>111</td><td>110</td><td>101</td><td>100</td><td>011</td><td>010</td><td>001</td><td>000</td></tr><tr><th>new state for center cell</th><td>1</td><td>0</td><td>1</td><td>1</td><td>1</td><td>0</td><td>0</td><td>0</td></tr></tbody></table>
An entry in this table defines the new state of each cell as a function of the previous state and the previous values of the neighboring cells on either side.
The name for this rule, Rule 184, is the <a href="/facts/Wolfram_code/bSKCzg0m">Wolfram code</a> describing the state table above: the bottom row of the table, 10111000, when viewed as a <a href="/facts/Binary_number/a6JDSRPs">binary number</a>, is equal to the decimal number <a href="/facts/184_(number)/2JUMGqdH">184</a>.<a class="footnote-ref" id="fnref:4" href="#fn:4">4</a>
The rule set for Rule 184 may also be described intuitively, in several different ways:

<ul><li>At each step, whenever there exists in the current state a 1 immediately followed by a 0, these two symbols swap places. Based on this description, Krug & Spohn (1988) call Rule 184 a deterministic version of a "kinetic <a href="/facts/Ising_model/lvBpj2h1">Ising model</a> with asymmetric spin-exchange dynamics".</li>
<li>At each step, if a cell with value 1 has a cell with value 0 immediately to its right, the 1 moves rightwards leaving a 0 behind. A 1 with another 1 to its right remains in place, while a 0 that does not have a 1 to its left stays a 0. This description is most apt for the application to traffic flow modeling.<a class="footnote-ref" id="fnref:5" href="#fn:5">5</a></li>
<li>If a cell has state 0, its new state is taken from the cell to its left. Otherwise, its new state is taken from the cell to its right. That is, each cell can be implemented by a two-way <a href="/facts/Demultiplexer/lVro0Sfz">demultiplexer</a> with the two adjacent cells being inputs, and the cell itself acting as the selector line. Each cell's next state is determined by the demultiplexer's output. This operation is closely related to a <a href="/facts/Fredkin_gate/mFmf5gqb">Fredkin gate</a>.<a class="footnote-ref" id="fnref:6" href="#fn:6">6</a></li></ul>
<h2 id="dynamics-and-majority-classification">Dynamics and majority classification</h2>
From the descriptions of the rules above, two important properties of its dynamics may immediately be seen. First, in Rule 184, for any finite set of cells with <a href="/facts/Periodic_boundary_conditions/8hdzjIAD">periodic boundary conditions</a>, the number of 1s and the number of 0s in a pattern remains invariant throughout the pattern's evolution. Rule 184 and its reflection are the only nontrivial<a class="footnote-ref" id="fnref:7" href="#fn:7">7</a> <a href="/facts/Elementary_cellular_automaton/mddSBmhy">elementary cellular automata</a> to have this property of number conservation.<a class="footnote-ref" id="fnref:8" href="#fn:8">8</a> Similarly, if the density of 1s is well-defined for an infinite array of cells, it remains invariant as the automaton carries out its steps.<a class="footnote-ref" id="fnref:9" href="#fn:9">9</a> And second, although Rule 184 is not symmetric under left-right reversal, it does have a different symmetry: reversing left and right and at the same time swapping the roles of the 0 and 1 symbols produces a cellular automaton with the same update rule.
Patterns in Rule 184 typically quickly stabilize, either to a pattern in which the cell states move in lockstep one position leftwards at each step, or to a pattern that moves one position rightwards at each step. Specifically, if the initial density of cells with state 1 is less than 50%, the pattern stabilizes into clusters of cells in state 1, spaced two units apart, with the clusters separated by blocks of cells in state 0. Patterns of this type move rightwards. If, on the other hand, the initial density is greater than 50%, the pattern stabilizes into clusters of cells in state 0, spaced two units apart, with the clusters separated by blocks of cells in state 1, and patterns of this type move leftwards. If the density is exactly 50%, the initial pattern stabilizes (more slowly) to a pattern that can equivalently be viewed as moving either leftwards or rightwards at each step: an alternating sequence of 0s and 1s.<a class="footnote-ref" id="fnref:10" href="#fn:10">10</a>
The <a href="/facts/Majority_problem_(cellular_automaton)/jvAH2tRQ">majority problem</a> is the problem of constructing a cellular automaton that, when run on any finite set of cells, can compute the value held by a majority of its cells.
In a sense, Rule 184 solves this problem, as follows. if Rule 184 is run on a finite set of cells with periodic boundary conditions, with an unequal number of 0s and 1s, then each cell will eventually see two consecutive states of the majority value infinitely often, but will see two consecutive states of the minority value only finitely many times.<a class="footnote-ref" id="fnref:11" href="#fn:11">11</a> The majority problem cannot be solved perfectly if it is required that all cells eventually stabilize to the majority state<a class="footnote-ref" id="fnref:12" href="#fn:12">12</a> but the Rule 184 solution avoids this impossibility result by relaxing the criterion by which the automaton recognizes a majority.

<h2 id="traffic-flow">Traffic flow</h2>

If one interprets each 1-cell in Rule 184 as containing a particle, these particles behave in many ways similarly to automobiles in a single lane of traffic: they move forward at a constant speed if there is open space in front of them, and otherwise they stop. Traffic models such as Rule 184 and its generalizations that discretize both space and time are commonly called particle-hopping models.<a class="footnote-ref" id="fnref:13" href="#fn:13">13</a> Although very primitive, the Rule 184 model of traffic flow already predicts some of the familiar emergent features of real traffic: clusters of freely moving cars separated by stretches of open road when traffic is light, and <a href="/facts/Traffic_wave/pVXnaBbg">waves of stop-and-go traffic</a> when it is heavy.<a class="footnote-ref" id="fnref:14" href="#fn:14">14</a>
It is difficult to pinpoint the first use of Rule 184 for traffic flow simulation, in part because the focus of research in this area has been less on achieving the greatest level of mathematical abstraction and more on verisimilitude: even the earlier papers on cellular automaton based traffic flow simulation typically make the model more complex in order to more accurately simulate real traffic. Nevertheless, Rule 184 is fundamental to traffic simulation by cellular automata. Wang, Kwong & Hui (1998), for instance, state that "the basic cellular automaton model describing a one-dimensional traffic flow problem is rule 184." Nagel (1996) writes "Much work using CA models for traffic is based on this model." Several authors describe one-dimensional models with vehicles moving at multiple speeds; such models degenerate to Rule 184 in the single-speed case.<a class="footnote-ref" id="fnref:15" href="#fn:15">15</a> Gaylord & Nishidate (1996) extend the Rule 184 dynamics to two-lane highway traffic with lane changes; their model shares with Rule 184 the property that it is symmetric under simultaneous left-right and 0-1 reversal. Biham, Middleton & Levine (1992) describe a <a href="/facts/Biham%E2%80%93Middleton%E2%80%93Levine_traffic_model/SGhtcpcy">two-dimensional city grid model</a> in which the dynamics of individual lanes of traffic is essentially that of Rule 184.<a class="footnote-ref" id="fnref:16" href="#fn:16">16</a> For an in-depth survey of cellular automaton traffic modeling and associated statistical mechanics, see Maerivoet & De Moor (2005) and Chowdhury, Santen & Schadschneider (2000).
When viewing Rule 184 as a traffic model, it is natural to consider the average speed of the vehicles. When the density of traffic is less than 50%, this average speed is simply one unit of distance per unit of time: after the system stabilizes, no car ever slows. However, when the density is a number ρ greater than 1/2, the average speed of traffic is 
 
 
 
 
 
 
 
 1
 −
 ρ
 
 ρ
 
 
 
 
 
 {\displaystyle {\tfrac {1-\rho }{\rho }}}
 
. Thus, the system exhibits a second-order kinetic <a href="/facts/Phase_transition/eLP2BY8R">phase transition</a> at ρ = 1/2. When Rule 184 is interpreted as a traffic model, and started from a random configuration whose density is at this critical value ρ = 1/2, then the average speed approaches its stationary limit as the square root of the number of steps. Instead, for random configurations whose density is not at the critical value, the approach to the limiting speed is exponential.<a class="footnote-ref" id="fnref:17" href="#fn:17">17</a>

<h2 id="surface-deposition">Surface deposition</h2>

As shown in the figure, and as originally described by Krug & Spohn (1988),<a class="footnote-ref" id="fnref:18" href="#fn:18">18</a> Rule 184 may be used to model deposition of particles onto a surface. In this model, one has a set of particles that occupy a subset of the positions in a <a href="/facts/Square_lattice/mcVtpcQK">square lattice</a> oriented diagonally (the darker particles in the figure). If a particle is present at some position of the lattice, the lattice positions below and to the right, and below and to the left of the particle must also be filled, so the filled part of the lattice extends infinitely downward to the left and right. The boundary between filled and unfilled positions (the thin black line in the figure) is interpreted as modeling a surface, onto which more particles may be deposited. At each time step, the surface grows by the deposition of new particles in each local minimum of the surface; that is, at each position where it is possible to add one new particle that has existing particles below it on both sides (the lighter particles in the figure).
To model this process by Rule 184, observe that the boundary between filled and unfilled lattice positions can be marked by a polygonal line, the segments of which separate adjacent lattice positions and have slopes +1 and −1. Model a segment with slope +1 by an automaton cell with state 0, and a segment with slope −1 by an automaton cell with state 1. The local minima of the surface are the points where a segment of slope −1 lies to the left of a segment of slope +1; that is, in the automaton, a position where a cell with state 1 lies to the left of a cell with state 0. Adding a particle to that position corresponds to changing the states of these two adjacent cells from 1,0 to 0,1, so advancing the polygonal line. This is exactly the behavior of Rule 184.<a class="footnote-ref" id="fnref:19" href="#fn:19">19</a>
Related work on this model concerns deposition in which the arrival times of additional particles are random, rather than having particles arrive at all local minima simultaneously.<a class="footnote-ref" id="fnref:20" href="#fn:20">20</a> These stochastic growth processes can be modeled as an <a href="/facts/Asynchronous_cellular_automaton/gLk6xs9J">asynchronous cellular automaton</a>.

<h2 id="ballistic-annihilation">Ballistic annihilation</h2>

Ballistic annihilation describes a process by which moving particles and <a href="/facts/Antiparticle/7Ic43ThI">antiparticles</a> <a href="/facts/Annihilation/tm55RWnf">annihilate</a> each other when they collide. In the simplest version of this process, the system consists of a single type of particle and antiparticle, moving at equal speeds in opposite directions in a one-dimensional medium.<a class="footnote-ref" id="fnref:21" href="#fn:21">21</a>
This process can be modeled by Rule 184, as follows. The particles are modeled as points that are aligned, not with the cells of the automaton, but rather with the interstices between cells. Two consecutive cells that both have state 0 model a particle at the space between these two cells that moves rightwards one cell at each time step. Symmetrically, two consecutive cells that both have state 1 model an antiparticle that moves leftwards one cell at each time step. The remaining possibilities for two consecutive cells are that they both have differing states; this is interpreted as modeling a background material without any particles in it, through which the particles move. With this interpretation, the particles and antiparticles interact by ballistic annihilation: when a rightwards-moving particle and a leftwards-moving antiparticle meet, the result is a region of background from which both particles have vanished, without any effect on any other nearby particles.<a class="footnote-ref" id="fnref:22" href="#fn:22">22</a>
The behavior of certain other systems, such as one-dimensional <a href="/facts/Cyclic_cellular_automaton/7eFuftoQ">cyclic cellular automata</a>, can also be described in terms of ballistic annihilation.<a class="footnote-ref" id="fnref:23" href="#fn:23">23</a> There is a technical restriction on the particle positions for the ballistic annihilation view of Rule 184 that does not arise in these other systems, stemming from the alternating pattern of the background: in the particle system corresponding to a Rule 184 state, if two consecutive particles are both of the same type they must be an odd number of cells apart, while if they are of opposite types they must be an even number of cells apart. However this parity restriction does not play a role in the statistical behavior of this system.
Pivato (2007) uses a similar but more complicated particle-system view of Rule 184: he not only views alternating 0–1 regions as background, but also considers regions consisting solely of a single state to be background as well. Based on this view he describes seven different particles formed by boundaries between regions, and classifies their possible interactions. See Chopard & Droz (1998, pp. 188–190) for a more general survey of the cellular automaton models of annihilation processes.

<h2 id="context-free-parsing">Context-free parsing</h2>
In his book <a href="/facts/A_New_Kind_of_Science/kqsM7RBp">A New Kind of Science</a>, <a href="/facts/Stephen_Wolfram/pJTChkGB">Stephen Wolfram</a> points out that rule 184, when run on patterns with density 50%, can be interpreted as parsing the <a href="/facts/Context-free_language/sHDxB5So">context-free language</a> describing strings formed from nested <a href="/facts/Bracket/yzGM9J8A">parentheses</a>. This interpretation is closely related to the ballistic annihilation view of rule 184: in Wolfram's interpretation, an open parenthesis corresponds to a left-moving particle while a close parenthesis corresponds to a right-moving particle.<a class="footnote-ref" id="fnref:24" href="#fn:24">24</a>

<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Rule_30/jzvVHHX2">Rule 30</a>, <a href="/facts/Rule_90/3U2Vmqqo">Rule 90</a>, and <a href="/facts/Rule_110/5LzC7FUK">Rule 110</a>, other one-dimensional cellular automata with different behavior</li></ul>
<h2 id="notes">Notes</h2>

<ul><li>Alonso-Sanz, Ramon (2011). <a href="https://books.google.com/books?id=UgnhKU9w3K8C&pg=PA55">"Number-preserving rules"</a>. Discrete Systems with Memory. World Scientific series on nonlinear science, Ser. A. Vol. 75. World Scientific. pp. 55–57. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 9789814343633.</li>
<li>Belitsky, Vladimir; Ferrari, Pablo A. (1995). "Ballistic annihilation and deterministic surface growth". <a href="/facts/Journal_of_Statistical_Physics/MbPMp5pA">Journal of Statistical Physics</a>. 80 (3–4): 517–543. <a href="/facts/Bibcode_(identifier)/9HtdQSGB">Bibcode</a>:<a href="https://ui.adsabs.harvard.edu/abs/1995JSP....80..517B">1995JSP....80..517B</a>. <a href="/facts/CiteSeerX_(identifier)/SceDmd3c">CiteSeerX</a> <a href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.4.7901">10.1.1.4.7901</a>. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2FBF02178546">10.1007/BF02178546</a>. <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:16293185">16293185</a>.</li>
<li><a href="/facts/Ofer_Biham/PH5jPg90">Biham, Ofer</a>; Middleton, A. Alan; Levine, Dov (1992). "Self-organization and a dynamic transition in traffic-flow models". <a href="/facts/Physical_Review_A/SyUn09fY">Physical Review A</a>. 46 (10): R6124 – R6127. <a href="/facts/ArXiv_(identifier)/H6EtgnBe">arXiv</a>:<a href="https://arxiv.org/abs/cond-mat/9206001">cond-mat/9206001</a>. <a href="/facts/Bibcode_(identifier)/9HtdQSGB">Bibcode</a>:<a href="https://ui.adsabs.harvard.edu/abs/1992PhRvA..46.6124B">1992PhRvA..46.6124B</a>. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1103%2FPhysRevA.46.R6124">10.1103/PhysRevA.46.R6124</a>. <a href="/facts/PMID_(identifier)/JlHAvMHt">PMID</a> <a href="https://pubmed.ncbi.nlm.nih.gov/9907993">9907993</a>. <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:14543020">14543020</a>.</li>
<li>Boccara, Nino; Fukś, Henryk (1998). "Cellular automaton rules conserving the number of active sites". <a href="/facts/Journal_of_Physics_A:_Mathematical_and_General/mC8blrqF">Journal of Physics A: Mathematical and General</a>. 31 (28): 6007–6018. <a href="/facts/ArXiv_(identifier)/H6EtgnBe">arXiv</a>:<a href="https://arxiv.org/abs/adap-org/9712003">adap-org/9712003</a>. <a href="/facts/Bibcode_(identifier)/9HtdQSGB">Bibcode</a>:<a href="https://ui.adsabs.harvard.edu/abs/1998JPhA...31.6007B">1998JPhA...31.6007B</a>. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1088%2F0305-4470%2F31%2F28%2F014">10.1088/0305-4470/31/28/014</a>. <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:14807539">14807539</a>.</li>
<li>Capcarrere, Mathieu S.; Sipper, Moshe; Tomassini, Marco (1996). <a href="http://www.cs.bgu.ac.il/~sipper/papabs/twostater1.pdf">"Two-state, r = 1 cellular automaton that classifies density"</a> (PDF). <a href="/facts/Physical_Review_Letters/rNP3XvYq">Physical Review Letters</a>. 77 (24): 4969–4971. <a href="/facts/Bibcode_(identifier)/9HtdQSGB">Bibcode</a>:<a href="https://ui.adsabs.harvard.edu/abs/1996PhRvL..77.4969C">1996PhRvL..77.4969C</a>. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1103%2FPhysRevLett.77.4969">10.1103/PhysRevLett.77.4969</a>. <a href="/facts/PMID_(identifier)/JlHAvMHt">PMID</a> <a href="https://pubmed.ncbi.nlm.nih.gov/10062680">10062680</a>.</li>
<li>Chopard, Bastien; Droz, Michel (1998). Cellular Automata Modeling of Physical Systems. <a href="/facts/Cambridge_University_Press/fgEBSSRq">Cambridge University Press</a>. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-0-521-67345-7.</li>
<li>Chowdhury, Debashish; Santen, Ludger; Schadschneider, Andreas (2000). "Statistical physics of vehicular traffic and some related systems". <a href="/facts/Physics_Reports/AjNs5QIf">Physics Reports</a>. 329 (4): 199–329. <a href="/facts/ArXiv_(identifier)/H6EtgnBe">arXiv</a>:<a href="https://arxiv.org/abs/cond-mat/0007053">cond-mat/0007053</a>. <a href="/facts/Bibcode_(identifier)/9HtdQSGB">Bibcode</a>:<a href="https://ui.adsabs.harvard.edu/abs/2000PhR...329..199C">2000PhR...329..199C</a>. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2FS0370-1573%2899%2900117-9">10.1016/S0370-1573(99)00117-9</a>. <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:119526662">119526662</a>.</li>
<li>Fukś, Henryk (1997). "Solution of the density classification problem with two similar cellular automata rules". <a href="/facts/Physical_Review_E/q3CNbGVd">Physical Review E</a>. 55 (3): R2081 – R2084. <a href="/facts/ArXiv_(identifier)/H6EtgnBe">arXiv</a>:<a href="https://arxiv.org/abs/comp-gas/9703001">comp-gas/9703001</a>. <a href="/facts/Bibcode_(identifier)/9HtdQSGB">Bibcode</a>:<a href="https://ui.adsabs.harvard.edu/abs/1997PhRvE..55.2081F">1997PhRvE..55.2081F</a>. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1103%2FPhysRevE.55.R2081">10.1103/PhysRevE.55.R2081</a>. <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:118954791">118954791</a>.</li>
<li>Fukś, Henryk; Boccara, Nino (1998). <a href="https://web.archive.org/web/20070927215541/http://www.tjhsst.edu/~ekoniecz/fuks.pdf">"Generalized deterministic traffic rules"</a> (PDF). <a href="/facts/International_Journal_of_Modern_Physics/sPJxLhT4">International Journal of Modern Physics C</a>. 9 (1): 1–12. <a href="/facts/ArXiv_(identifier)/H6EtgnBe">arXiv</a>:<a href="https://arxiv.org/abs/adap-org/9705003">adap-org/9705003</a>. <a href="/facts/Bibcode_(identifier)/9HtdQSGB">Bibcode</a>:<a href="https://ui.adsabs.harvard.edu/abs/1998IJMPC...9....1F">1998IJMPC...9....1F</a>. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1142%2FS0129183198000029">10.1142/S0129183198000029</a>. <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:119938282">119938282</a>. Archived from <a href="http://www.tjhsst.edu/~ekoniecz/fuks.pdf">the original</a> (PDF) on 27 September 2007.</li>
<li>Fukui, M.; Ishibashi, Y. (1996). "Traffic flow in 1D cellular automaton model including cars moving with high speed". <a href="/facts/Journal_of_the_Physical_Society_of_Japan/ydTtBVR6">Journal of the Physical Society of Japan</a>. 65 (6): 1868–1870. <a href="/facts/Bibcode_(identifier)/9HtdQSGB">Bibcode</a>:<a href="https://ui.adsabs.harvard.edu/abs/1996JPSJ...65.1868F">1996JPSJ...65.1868F</a>. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1143%2FJPSJ.65.1868">10.1143/JPSJ.65.1868</a>.</li>
<li>Gaylord, Richard J.; Nishidate, Kazume (1996). "Traffic Flow". <a href="https://archive.org/details/modelingnaturece00gayl/page/29">Modeling Nature: Cellular Automata Simulations with Mathematica</a>. <a href="/facts/Springer-Verlag/nAesf6nT">Springer-Verlag</a>. pp. <a href="https://archive.org/details/modelingnaturece00gayl/page/29">29–34</a>. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-0-387-94620-7.</li>
<li>Krug, J.; Spohn, H. (1988). "Universality classes for deterministic surface growth". <a href="/facts/Physical_Review_A/SyUn09fY">Physical Review A</a>. 38 (8): 4271–4283. <a href="/facts/Bibcode_(identifier)/9HtdQSGB">Bibcode</a>:<a href="https://ui.adsabs.harvard.edu/abs/1988PhRvA..38.4271K">1988PhRvA..38.4271K</a>. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1103%2FPhysRevA.38.4271">10.1103/PhysRevA.38.4271</a>. <a href="/facts/PMID_(identifier)/JlHAvMHt">PMID</a> <a href="https://pubmed.ncbi.nlm.nih.gov/9900880">9900880</a>.</li>
<li>Land, Mark; Belew, Richard (1995). "No perfect two-state cellular automata for density classification exists". <a href="/facts/Physical_Review_Letters/rNP3XvYq">Physical Review Letters</a>. 74 (25): 1548–1550. <a href="/facts/Bibcode_(identifier)/9HtdQSGB">Bibcode</a>:<a href="https://ui.adsabs.harvard.edu/abs/1995PhRvL..74.5148L">1995PhRvL..74.5148L</a>. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1103%2FPhysRevLett.74.5148">10.1103/PhysRevLett.74.5148</a>. <a href="/facts/PMID_(identifier)/JlHAvMHt">PMID</a> <a href="https://pubmed.ncbi.nlm.nih.gov/10058695">10058695</a>.</li>
<li>Li, Wentian (1987). <a href="https://web.archive.org/web/20071007061217/http://www.nslij-genetics.org/wli/pub/cs87-no-figure.pdf">"Power spectra of regular languages and cellular automata"</a> (PDF). <a href="/facts/Complex_Systems_(journal)/gu7S6gIt">Complex Systems</a>. 1: 107–130. Archived from <a href="http://www.nslij-genetics.org/wli/pub/cs87-no-figure.pdf">the original</a> (PDF) on 2007-10-07.</li>
<li>Li, Wentian (1992). "Phenomenology of nonlocal cellular automata". <a href="/facts/Journal_of_Statistical_Physics/MbPMp5pA">Journal of Statistical Physics</a>. 68 (5–6): 829–882. <a href="/facts/Bibcode_(identifier)/9HtdQSGB">Bibcode</a>:<a href="https://ui.adsabs.harvard.edu/abs/1992JSP....68..829L">1992JSP....68..829L</a>. <a href="/facts/CiteSeerX_(identifier)/SceDmd3c">CiteSeerX</a> <a href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.590.1708">10.1.1.590.1708</a>. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2FBF01048877">10.1007/BF01048877</a>. <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:17337112">17337112</a>.</li>
<li>Maerivoet, Sven; De Moor, Bart (2005). "Cellular automata models of road traffic". <a href="/facts/Physics_Reports/AjNs5QIf">Physics Reports</a>. 419 (1): 1–64. <a href="/facts/ArXiv_(identifier)/H6EtgnBe">arXiv</a>:<a href="https://arxiv.org/abs/physics/0509082">physics/0509082</a>. <a href="/facts/Bibcode_(identifier)/9HtdQSGB">Bibcode</a>:<a href="https://ui.adsabs.harvard.edu/abs/2005PhR...419....1M">2005PhR...419....1M</a>. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2Fj.physrep.2005.08.005">10.1016/j.physrep.2005.08.005</a>. <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:41394950">41394950</a>.</li>
<li>Moreira, Andres (2003). "Universality and decidability of number-conserving cellular automata". <a href="/facts/Theoretical_Computer_Science_(journal)/Apbc0PDL">Theoretical Computer Science</a>. 292 (3): 711–721. <a href="/facts/ArXiv_(identifier)/H6EtgnBe">arXiv</a>:<a href="https://arxiv.org/abs/nlin.CG/0306032">nlin.CG/0306032</a>. <a href="/facts/Bibcode_(identifier)/9HtdQSGB">Bibcode</a>:<a href="https://ui.adsabs.harvard.edu/abs/2003nlin......6032M">2003nlin......6032M</a>. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2FS0304-3975%2802%2900065-8">10.1016/S0304-3975(02)00065-8</a>. <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:14909462">14909462</a>.</li>
<li>Nagel, Kai (1996). "Particle hopping models and traffic flow theory". <a href="/facts/Physical_Review_E/q3CNbGVd">Physical Review E</a>. 53 (5): 4655–4672. <a href="/facts/ArXiv_(identifier)/H6EtgnBe">arXiv</a>:<a href="https://arxiv.org/abs/cond-mat/9509075">cond-mat/9509075</a>. <a href="/facts/Bibcode_(identifier)/9HtdQSGB">Bibcode</a>:<a href="https://ui.adsabs.harvard.edu/abs/1996PhRvE..53.4655N">1996PhRvE..53.4655N</a>. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1103%2FPhysRevE.53.4655">10.1103/PhysRevE.53.4655</a>. <a href="/facts/PMID_(identifier)/JlHAvMHt">PMID</a> <a href="https://pubmed.ncbi.nlm.nih.gov/9964794">9964794</a>. <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:20466753">20466753</a>.</li>
<li>Nagel, Kai; Schreckenberg, Michael (1992). <a href="https://hal.archives-ouvertes.fr/jpa-00246697/document">"A cellular automaton model for freeway traffic"</a>. Journal de Physique I. 2 (12): 2221–2229. <a href="/facts/Bibcode_(identifier)/9HtdQSGB">Bibcode</a>:<a href="https://ui.adsabs.harvard.edu/abs/1992JPhy1...2.2221N">1992JPhy1...2.2221N</a>. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1051%2Fjp1%3A1992277">10.1051/jp1:1992277</a>. <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:37135830">37135830</a>.</li>
<li>Pivato, M. (2007). "Defect particle kinematics in one-dimensional cellular automata". <a href="/facts/Theoretical_Computer_Science_(journal)/Apbc0PDL">Theoretical Computer Science</a>. 377 (1–3): 205–228. <a href="/facts/ArXiv_(identifier)/H6EtgnBe">arXiv</a>:<a href="https://arxiv.org/abs/math.DS/0506417">math.DS/0506417</a>. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2Fj.tcs.2007.03.014">10.1016/j.tcs.2007.03.014</a>. <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:12650387">12650387</a>.</li>
<li>Redner, Sidney (2001). <a href="https://books.google.com/books?id=xtsqMh3VC98C&pg=PA288">"8.5 Ballistic Annihilation"</a>. A Guide to First-Passage Processes. <a href="/facts/Cambridge_University_Press/fgEBSSRq">Cambridge University Press</a>. p. 288. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 9780521652483.</li>
<li>Sukumar, N. (1998). "Effect of boundary conditions on cellular automata that classify density". <a href="/facts/ArXiv_(identifier)/H6EtgnBe">arXiv</a>:<a href="https://arxiv.org/abs/comp-gas/9804001">comp-gas/9804001</a>.</li>
<li>Tadaki, Shin-ichi; Kikuchi, Macato (1994). "Jam phases in a two-dimensional cellular automaton model of traffic flow". <a href="/facts/Physical_Review_E/q3CNbGVd">Physical Review E</a>. 50 (6): 4564–4570. <a href="/facts/ArXiv_(identifier)/H6EtgnBe">arXiv</a>:<a href="https://arxiv.org/abs/patt-sol/9409004">patt-sol/9409004</a>. <a href="/facts/Bibcode_(identifier)/9HtdQSGB">Bibcode</a>:<a href="https://ui.adsabs.harvard.edu/abs/1994PhRvE..50.4564T">1994PhRvE..50.4564T</a>. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1103%2FPhysRevE.50.4564">10.1103/PhysRevE.50.4564</a>. <a href="/facts/PMID_(identifier)/JlHAvMHt">PMID</a> <a href="https://pubmed.ncbi.nlm.nih.gov/9962535">9962535</a>. <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:17516156">17516156</a>.</li>
<li>Wang, Bing-Hong; Kwong, Yvonne-Roamy; Hui, Pak-Ming (1998). "Statistical mechanical approach to Fukui-Ishibashi traffic flow models". <a href="/facts/Physical_Review_E/q3CNbGVd">Physical Review E</a>. 57 (3): 2568–2573. <a href="/facts/Bibcode_(identifier)/9HtdQSGB">Bibcode</a>:<a href="https://ui.adsabs.harvard.edu/abs/1998PhRvE..57.2568W">1998PhRvE..57.2568W</a>. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1103%2FPhysRevE.57.2568">10.1103/PhysRevE.57.2568</a>.</li>
<li><a href="/facts/Stephen_Wolfram/pJTChkGB">Wolfram, Stephen</a> (2002). <a href="/facts/A_New_Kind_of_Science/kqsM7RBp">A New Kind of Science</a>. <a href="/facts/Wolfram_Media/rDU0dXdE">Wolfram Media</a>.</li></ul>

<h2 id="external-links">External links</h2>

Wikimedia Commons has media related to Rule 184.

<ul><li><a href="http://atlas.wolfram.com/01/01/184/">Rule 184 in Wolfram's atlas of cellular automata</a></li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">E.g. see Fukś (1997). - Fukś, Henryk (1997). "Solution of the density classification problem with two similar cellular automata rules". Physical Review E. 55 (3): R2081 – R2084. arXiv:comp-gas/9703001. Bibcode:1997PhRvE..55.2081F. doi:10.1103/PhysRevE.55.R2081. S2CID 118954791. <a href="https://arxiv.org/abs/comp-gas/9703001" target="_blank">https://arxiv.org/abs/comp-gas/9703001</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">One can find many later papers that, when mentioning Rule 184, cite the early papers of Stephen Wolfram. However, Wolfram's papers consider only automata that are symmetric under left-right reversal, and therefore do not describe Rule 184. <a href="/wiki/Stephen_Wolfram" target="_blank">/wiki/Stephen_Wolfram</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">This rule table is already given in a shorthand form in the name "Rule 184", but it can be found explicitly e.g. in Fukś (1997). - Fukś, Henryk (1997). "Solution of the density classification problem with two similar cellular automata rules". Physical Review E. 55 (3): R2081 – R2084. arXiv:comp-gas/9703001. Bibcode:1997PhRvE..55.2081F. doi:10.1103/PhysRevE.55.R2081. S2CID 118954791. <a href="https://arxiv.org/abs/comp-gas/9703001" target="_blank">https://arxiv.org/abs/comp-gas/9703001</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">For the definition of this code, see Wolfram (2002), p.53. For the calculation of this code for Rule 184, see e.g. Boccara & Fukś (1998). - Wolfram, Stephen (2002). A New Kind of Science. Wolfram Media. <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">See, e.g., Boccara & Fukś (1998). - Boccara, Nino; Fukś, Henryk (1998). "Cellular automaton rules conserving the number of active sites". Journal of Physics A: Mathematical and General. 31 (28): 6007–6018. arXiv:adap-org/9712003. Bibcode:1998JPhA...31.6007B. doi:10.1088/0305-4470/31/28/014. S2CID 14807539. <a href="https://arxiv.org/abs/adap-org/9712003" target="_blank">https://arxiv.org/abs/adap-org/9712003</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">Li (1992). Li used this interpretation as part of a generalization of Rule 184 to nonlocal neighborhood structures. - Li, Wentian (1992). "Phenomenology of nonlocal cellular automata". Journal of Statistical Physics. 68 (5–6): 829–882. Bibcode:1992JSP....68..829L. CiteSeerX 10.1.1.590.1708. doi:10.1007/BF01048877. S2CID 17337112. <a href="https://ui.adsabs.harvard.edu/abs/1992JSP....68..829L" target="_blank">https://ui.adsabs.harvard.edu/abs/1992JSP....68..829L</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">Rules 170, 204, and 240 trivially exhibit this property, as in each of these rules, every cell is simply copied from one of the three cells above it on each step. <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
<li id="fn:8">Boccara & Fukś (1998); Alonso-Sanz (2011). - Boccara, Nino; Fukś, Henryk (1998). "Cellular automaton rules conserving the number of active sites". Journal of Physics A: Mathematical and General. 31 (28): 6007–6018. arXiv:adap-org/9712003. Bibcode:1998JPhA...31.6007B. doi:10.1088/0305-4470/31/28/014. S2CID 14807539. <a href="https://arxiv.org/abs/adap-org/9712003" target="_blank">https://arxiv.org/abs/adap-org/9712003</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
<li id="fn:9">Boccara & Fukś (1998) have investigated more general automata with similar conservation properties, as has Moreira (2003). - Boccara, Nino; Fukś, Henryk (1998). "Cellular automaton rules conserving the number of active sites". Journal of Physics A: Mathematical and General. 31 (28): 6007–6018. arXiv:adap-org/9712003. Bibcode:1998JPhA...31.6007B. doi:10.1088/0305-4470/31/28/014. S2CID 14807539. <a href="https://arxiv.org/abs/adap-org/9712003" target="_blank">https://arxiv.org/abs/adap-org/9712003</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></li>
<li id="fn:10">Li (1987). - Li, Wentian (1987). "Power spectra of regular languages and cellular automata" (PDF). Complex Systems. 1: 107–130. Archived from the original (PDF) on 2007-10-07. <a href="https://web.archive.org/web/20071007061217/http://www.nslij-genetics.org/wli/pub/cs87-no-figure.pdf" target="_blank">https://web.archive.org/web/20071007061217/http://www.nslij-genetics.org/wli/pub/cs87-no-figure.pdf</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></li>
<li id="fn:11">Capcarrere, Sipper & Tomassini (1996); Fukś (1997); Sukumar (1998). - Capcarrere, Mathieu S.; Sipper, Moshe; Tomassini, Marco (1996). "Two-state, r = 1 cellular automaton that classifies density" (PDF). Physical Review Letters. 77 (24): 4969–4971. Bibcode:1996PhRvL..77.4969C. doi:10.1103/PhysRevLett.77.4969. PMID 10062680. <a href="http://www.cs.bgu.ac.il/~sipper/papabs/twostater1.pdf" target="_blank">http://www.cs.bgu.ac.il/~sipper/papabs/twostater1.pdf</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></li>
<li id="fn:12">Land & Belew (1995). - Land, Mark; Belew, Richard (1995). "No perfect two-state cellular automata for density classification exists". Physical Review Letters. 74 (25): 1548–1550. Bibcode:1995PhRvL..74.5148L. doi:10.1103/PhysRevLett.74.5148. PMID 10058695. <a href="https://ui.adsabs.harvard.edu/abs/1995PhRvL..74.5148L" target="_blank">https://ui.adsabs.harvard.edu/abs/1995PhRvL..74.5148L</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></li>
<li id="fn:13">Nagel (1996); Chowdhury, Santen & Schadschneider (2000). - Nagel, Kai (1996). "Particle hopping models and traffic flow theory". Physical Review E. 53 (5): 4655–4672. arXiv:cond-mat/9509075. Bibcode:1996PhRvE..53.4655N. doi:10.1103/PhysRevE.53.4655. PMID 9964794. S2CID 20466753. <a href="https://arxiv.org/abs/cond-mat/9509075" target="_blank">https://arxiv.org/abs/cond-mat/9509075</a> <a href="#fnref:13" class="footnote-back-ref">↩</a></li>
<li id="fn:14">Tadaki & Kikuchi (1994). - Tadaki, Shin-ichi; Kikuchi, Macato (1994). "Jam phases in a two-dimensional cellular automaton model of traffic flow". Physical Review E. 50 (6): 4564–4570. arXiv:patt-sol/9409004. Bibcode:1994PhRvE..50.4564T. doi:10.1103/PhysRevE.50.4564. PMID 9962535. S2CID 17516156. <a href="https://arxiv.org/abs/patt-sol/9409004" target="_blank">https://arxiv.org/abs/patt-sol/9409004</a> <a href="#fnref:14" class="footnote-back-ref">↩</a></li>
<li id="fn:15">For several models of this type see Nagel & Schreckenberg (1992), Fukui & Ishibashi (1996), and Fukś & Boccara (1998). Nagel (1996) observes the equivalence of these models to rule 184 in the single-speed case and lists several additional papers on this type of model. - Nagel, Kai; Schreckenberg, Michael (1992). "A cellular automaton model for freeway traffic". Journal de Physique I. 2 (12): 2221–2229. Bibcode:1992JPhy1...2.2221N. doi:10.1051/jp1:1992277. S2CID 37135830. <a href="https://hal.archives-ouvertes.fr/jpa-00246697/document" target="_blank">https://hal.archives-ouvertes.fr/jpa-00246697/document</a> <a href="#fnref:15" class="footnote-back-ref">↩</a></li>
<li id="fn:16">See also Tadaki & Kikuchi (1994) for additional analysis of this model. - Tadaki, Shin-ichi; Kikuchi, Macato (1994). "Jam phases in a two-dimensional cellular automaton model of traffic flow". Physical Review E. 50 (6): 4564–4570. arXiv:patt-sol/9409004. Bibcode:1994PhRvE..50.4564T. doi:10.1103/PhysRevE.50.4564. PMID 9962535. S2CID 17516156. <a href="https://arxiv.org/abs/patt-sol/9409004" target="_blank">https://arxiv.org/abs/patt-sol/9409004</a> <a href="#fnref:16" class="footnote-back-ref">↩</a></li>
<li id="fn:17">Fukś & Boccara (1998). - Fukś, Henryk; Boccara, Nino (1998). "Generalized deterministic traffic rules" (PDF). International Journal of Modern Physics C. 9 (1): 1–12. arXiv:adap-org/9705003. Bibcode:1998IJMPC...9....1F. doi:10.1142/S0129183198000029. S2CID 119938282. Archived from the original (PDF) on 27 September 2007. <a href="https://web.archive.org/web/20070927215541/http://www.tjhsst.edu/~ekoniecz/fuks.pdf" target="_blank">https://web.archive.org/web/20070927215541/http://www.tjhsst.edu/~ekoniecz/fuks.pdf</a> <a href="#fnref:17" class="footnote-back-ref">↩</a></li>
<li id="fn:18">See also Belitsky & Ferrari (1995) and Chopard & Droz (1998, p. 29). - Belitsky, Vladimir; Ferrari, Pablo A. (1995). "Ballistic annihilation and deterministic surface growth". Journal of Statistical Physics. 80 (3–4): 517–543. Bibcode:1995JSP....80..517B. CiteSeerX 10.1.1.4.7901. doi:10.1007/BF02178546. S2CID 16293185. <a href="https://ui.adsabs.harvard.edu/abs/1995JSP....80..517B" target="_blank">https://ui.adsabs.harvard.edu/abs/1995JSP....80..517B</a> <a href="#fnref:18" class="footnote-back-ref">↩</a></li>
<li id="fn:19">Krug & Spohn (1988). - Krug, J.; Spohn, H. (1988). "Universality classes for deterministic surface growth". Physical Review A. 38 (8): 4271–4283. Bibcode:1988PhRvA..38.4271K. doi:10.1103/PhysRevA.38.4271. PMID 9900880. <a href="https://ui.adsabs.harvard.edu/abs/1988PhRvA..38.4271K" target="_blank">https://ui.adsabs.harvard.edu/abs/1988PhRvA..38.4271K</a> <a href="#fnref:19" class="footnote-back-ref">↩</a></li>
<li id="fn:20">Also discussed by Krug & Spohn (1988). - Krug, J.; Spohn, H. (1988). "Universality classes for deterministic surface growth". Physical Review A. 38 (8): 4271–4283. Bibcode:1988PhRvA..38.4271K. doi:10.1103/PhysRevA.38.4271. PMID 9900880. <a href="https://ui.adsabs.harvard.edu/abs/1988PhRvA..38.4271K" target="_blank">https://ui.adsabs.harvard.edu/abs/1988PhRvA..38.4271K</a> <a href="#fnref:20" class="footnote-back-ref">↩</a></li>
<li id="fn:21">Redner (2001). - Redner, Sidney (2001). "8.5 Ballistic Annihilation". A Guide to First-Passage Processes. Cambridge University Press. p. 288. ISBN 9780521652483. <a href="https://books.google.com/books?id=xtsqMh3VC98C&pg=PA288" target="_blank">https://books.google.com/books?id=xtsqMh3VC98C&pg=PA288</a> <a href="#fnref:21" class="footnote-back-ref">↩</a></li>
<li id="fn:22">Krug & Spohn (1988); Belitsky & Ferrari (1995). - Krug, J.; Spohn, H. (1988). "Universality classes for deterministic surface growth". Physical Review A. 38 (8): 4271–4283. Bibcode:1988PhRvA..38.4271K. doi:10.1103/PhysRevA.38.4271. PMID 9900880. <a href="https://ui.adsabs.harvard.edu/abs/1988PhRvA..38.4271K" target="_blank">https://ui.adsabs.harvard.edu/abs/1988PhRvA..38.4271K</a> <a href="#fnref:22" class="footnote-back-ref">↩</a></li>
<li id="fn:23">Belitsky & Ferrari (1995). - Belitsky, Vladimir; Ferrari, Pablo A. (1995). "Ballistic annihilation and deterministic surface growth". Journal of Statistical Physics. 80 (3–4): 517–543. Bibcode:1995JSP....80..517B. CiteSeerX 10.1.1.4.7901. doi:10.1007/BF02178546. S2CID 16293185. <a href="https://ui.adsabs.harvard.edu/abs/1995JSP....80..517B" target="_blank">https://ui.adsabs.harvard.edu/abs/1995JSP....80..517B</a> <a href="#fnref:23" class="footnote-back-ref">↩</a></li>
<li id="fn:24">Wolfram (2002, pp. 989, 1109). - Wolfram, Stephen (2002). A New Kind of Science. Wolfram Media. <a href="#fnref:24" class="footnote-back-ref">↩</a></li>
</ol>

Rule 184 open-in-new

Rule 184