- Rule 184
**Rule 184**is a one-dimensional binarycellular automaton rule, notable for solving the majority problem as well as for its ability to simultaneously describe several, seemingly quite different,particle system s:* Rule 184 can be used as a simple model for

traffic flow in a single lane of a highway, and forms the basis for many cellular automaton models of traffic flow with greater sophistication. In this model, particles (representing vehicles) move in a single direction, stopping and starting depending on the cars in front of them. The number of particles remains unchanged throughout the simulation. Because of this application, Rule 184 is sometimes called the "traffic rule." [*E.g. see Fukś (1997).*]

* Rule 184 also models a form of deposition of particles onto an irregular surface, in which each local minimum of the surface is filled with a particle in each step. At each step of the simulation, the number of particles increases. Once placed, a particle never moves.

* Rule 184 can be understood in terms ofballistic annihilation , a system of particles moving both leftwards and rightwards through a one-dimensional medium. When two such particles collide, theyannihilate each other, so that at each step the number of particles remains unchanged or decreases.The apparent contradiction between these descriptions is resolved by different ways of corresponding features of the automaton's state with particles.In each step of its evolution, the Rule 184 automaton applies the following rule to determine the new state of each cell, in a one-dimensional array of cells:

current pattern 111 110 101 100 011 010 001 000 new state for center cell 1 0 1 1 1 0 0 0

The name for this rule, Rule 184, is theWolfram code describing the state table above: the bottom row of the table, 10111000, when viewed as abinary number , is equal to the decimal number 184. The earliest research on Rule 184 seems to be the papers by Li (1987) and Krug and Spohn (1988). In particular, Krug and Spohn already describe all three types of particle system modeled by Rule 184. [*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.**Equivalent description of rules**The rule set for Rule 184 may be described using a table, as above, but it may also be described intuitively, in several different ways:

*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 and Spohn (1984) call Rule 184 a deterministic version of a "kineticIsing model with asymmetric spin-exchange dynamics".

*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.

*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 amultiplexer , and is closely related in its operation to aFredkin gate . [*Li (1992). Li used this interpretation as part of a generalization of Rule 184 to nonlocal neighborhood structures.*]**Dynamics and majority classification**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

periodic boundary conditions , the number of 1s and the number of 0s in a pattern remains invariant throughout the pattern's evolution. 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. [*Boccara and Fukś (1998) have investigated more general automata with similar conservation properties, as has Moreira (2003).*] 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. [

*Li (1987).*] 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 1, spaced two units apart, with the clusters separated by blocks of cells in state 0, 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.One can view Rule 184 as solving the majority problem, of constructing a cellular automaton that can determine whether an initial configuration has a majority of its cells active: if Rule 184 is run on a finite set of cells with periodic boundary conditions, and the number of active cells is less than half of all cells, then each cell will eventually see two consecutive zero states infinitely often, and two consecutive one states only finitely often, while if the number of active cells forms a majority of the cells then each cell will eventually see two consecutive ones infinitely often and two consecutive zeros only finitely often. [

*Capcarrere et al. (1996); Fukś (1997); Sukumar (1998).*] The majority problem cannot be solved perfectly if it is required that all cells eventually stabilize to the majority state [*Land and Belew (1995).*] but the Rule 184 solution avoids this impossibility result by relaxing the criterion by which the automaton recognizes a majority.**Traffic flow**If we interpret 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 forwards 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". [

*Nagel (1996); Chowdhury et al. (2000).*] 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 waves of stop-and-go traffic when it is heavy. [*Tadaki and Kikuchi (1994).*]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 et al. (1997), 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. [

*For several models of this type see Nagel and Schreckenberg (1992), Fukui and Ishibashi (1996), and Fukś and 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.*] Gaylord and 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 et al. (1992) describe a two-dimensional city grid model in which the dynamics of individual lanes of traffic is essentially that of Rule 184. [*See also Tadaki and Kikuchi (1994) for additional analysis of this model.*] For an in-depth survey of cellular automaton traffic modeling and associated statistical mechanics, see Chowdhury et al. (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 $frac\{1-\; ho\}\{\; ho\}$. Thus, the system exhibits a second-order kinetic

phase transition at ρ = 1/2. At that critical value the average speed approaches its stationary limit as the square root of the number of steps, while away from the critical value the approach is exponential. [*Fukś and Boccara (1998).*]**urface deposition**As shown in the figure, and as originally described by Krug and Spohn (1988), [

*See also Belitzky and Ferrari (1995) and Chopard and Droz (1998, p. 29).*] Rule 184 may be used to model deposition of particles onto a surface. In this model, one has a set of particles forming a surface, where the particles assume positions in asquare lattice oriented diagonally. 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. At each time step, the surface grows by the deposition of particles in each local minimum of the surface; that is, at each position where it is possible to add a new particle. To model this process by Rule 184, we 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. We 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, which is exactly the behavior of Rule 184.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. [

*Also discussed by Krug and Spohn (1988).*] These stochastic growth processes can be modeled as anasynchronous cellular automaton .**Ballistic annihilation**Ballistic annihilation describes a process by which moving particles andantiparticle sannihilate 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.This process can be modeled by Rule 184, as follows. We view the particles as aligned, not with the cells of the automaton, but rather with the interstices between cells. If two consecutive cells both have state 0, we view the transition between them as forming a particle that moves rightwards one cell at each time step. If, on the other hand, two consecutive cells both have state 1, we view the transition between them as forming an antiparticle that moves leftwards one cell at each time step. Two consecutive cells with differing states are considered to form part of a background material without any particles in it. It may be observed that these particles 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. [

*Krug and Spohn (1988); Belitzky and Ferrari (1995).*]The behavior of certain other systems, such as one-dimensional cyclic cellular automata, can also be described in terms of ballistic annihilation. [

*Belitzky and Ferrari (1995).*] 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 (2005) 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 and Droz (1998, pp. 188–190) for a more general survey of the physics of annihilation processes.

**Context free parsing**In his book

A New Kind of Science ,Stephen Wolfram points out that rule 184, when run on patterns with density 50%, can be interpreted as parsing thecontext free language describing strings formed from nested parentheses. 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.**Notes****References**

*cite journal

author = Belitsky, Vladimir; Ferrari, Pablo A.

title = Ballistic annihilation and deterministic surface growth

journal = Journal of Statistical Physics

volume = 80

issue = 3–4

year = 1995

pages = 517–543

doi = 10.1007/BF02178546

*cite journal

author = Biham, Ofer; Middleton, A. Alan; Levine, Dov

title = Self-organization and a dynamic transition in traffic-flow models

journal = Physical Review A

volume = 46

issue = 10

year = 1992

pages = R6124–R6127

doi = 10.1103/PhysRevA.46.R6124*cite journal

author = Boccara, Nino; Fukś, Henryk

title = Cellular automaton rules conserving the number of active sites

journal = J. Phys. A: Math. Gen.

volume = 31

issue = 28

pages = 6007–6018

year = 1998

doi = 10.1088/0305-4470/31/28/014

id = arxiv|adap-org|9712003*cite journal

author = Capcarrere, Mathieu S.; Sipper, Moshe; Tomassini, Marco

title = Two-state, "r" = 1 cellular automaton that classifies density

journal = Phys. Rev. Lett.

year = 1996

volume = 77

pages = 4969

url = http://www.leitl.org/docs/density.ps.gz

doi = 10.1103/PhysRevLett.77.4969*cite book

author = Chopard, Bastien; Droz, Michel

title = Cellular Automata Modeling of Physical Systems

year = 1998

publisher = Cambridge University Press

id = ISBN 0-521-67345-3*cite journal

author = Chowdhury, Debashish; Santen, Ludger; Schadschneider, Andreas

title = Statistical physics of vehicular traffic and some related systems

journal = Physics Reports

volume = 329

issue = 4

pages = 199–329

year = 2000

doi = 10.1016/S0370-1573(99)00117-9

id = arxiv|cond-mat|0007053*cite journal

author = Fukś, Henryk

title = Solution of the density classification problem with two similar cellular automata rules

journal = Physical Review E

volume = 55

issue = 3

pages = R2081–R2084

year = 1997

doi = 10.1103/PhysRevE.55.R2081*cite journal

author = Fukś, Henryk; Boccara, Nino

title = Generalized deterministic traffic rules

journal = Journal of Modern Physics C

volume = 9

issue = 1

year = 1998

pages = 1–12

url = http://www.tjhsst.edu/~ekoniecz/fuks.pdf

doi = 10.1142/S0129183198000029*cite journal

author = Fukui, M.; Ishibashi, Y.

title = Traffic flow in 1D cellular automaton model including cars moving with high speed

journal = J. Phys. Soc. Japan

volume = 65

issue = 6

pages = 1868–1870

doi = 10.1143/JPSJ.65.1868

year = 1996*cite book

author = Gaylord, Richard J.; Nishidate, Kazume

title = Modeling Nature: Cellular Automata Simulations with "Mathematica"

publisher = Springer-Verlag

year = 1996

pages = 29–35

id = ISBN 978-0387946207*cite journal

author = Krug, J.; Spohn, H.

title = Universality classes for deterministic surface growth

journal = Physical Review A

volume = 38

issue = 8

pages = 4271–4283

year = 1988

doi = 10.1103/PhysRevA.38.4271*cite journal

author = Land, Mark; Belew, Richard

title = No perfect two-state cellular automata for density classification exists

journal = Physical Review Letters

volume = 74

issue = 25

year = 1995

pages = 1548–1550

doi = 10.1103/PhysRevLett.74.5148*cite journal

author = Li, Wentian

title = Power spectra of regular languages and cellular automata

journal = Complex Systems

volume = 1

pages = 107–130

year = 1987

url = http://www.nslij-genetics.org/wli/pub/cs87-no-figure.pdf*cite journal

author = Li, Wentian

title = Phenomenology of nonlocal cellular automata

journal = Journal of Statistical Physics

volume = 68

issue = 5–6

pages = 829–882

year = 1992

doi = 10.1007/BF01048877

*cite journal

author = Moreira, Andres

title = Universality and decidability of number-conserving cellular automata

journal = Theoretical Computer Science

volume = 292

pages = 711–721

year = 2003

id = arxiv|nlin.CG|0306032

doi = 10.1016/S0304-3975(02)00065-8

*cite journal

author = Nagel, Kai

title = Particle hopping models and traffic flow theory

year = 1996

journal = Physical Review E

volume = 53

issue = 5

pages = 4655–4672

doi = 10.1103/PhysRevE.53.4655

*cite journal

author = Nagel, Kai; Schreckenberg, Michael

title = A cellular automaton model for freeway traffic

journal = Journal de Physique I

volume = 2

pages = 2221–2229

year = 1992

doi = 10.1051/jp1:1992277*cite journal

author = Pivato, M.

title = Defect particle kinematics in one-dimensional cellular automata

year = 2005

id = arxiv|math.DS|0506417*cite journal

author = Sukumar, N.

title = Effect of boundary conditions on cellular automata that classify density

year = 1998

id = arxiv|comp-gas|9804001*cite journal

author = Tadaki, Shin-ichi; Kikuchi, Macato

title = Jam phases in a two-dimensional cellular automaton model of traffic flow

journal = Physical Review E

volume = 50

number = 6

year = 1994

pages = 4564–4570

doi = 10.1103/PhysRevE.50.4564

*cite journal

author = Wang, Bing-Hong; Kwong, Yvonne-Roamy; Hui, Pak-Ming

title = Statistical mechanical approach to Fukui-Ishibashi traffic flow models

journal = Physical Review E

volume = 57

issue = 3

year = 1998

pages = 2568–2573

doi = 10.1103/PhysRevE.57.2568*

Stephen Wolfram , [*http://www.wolframscience.com/nksonline/page-707 "A New Kind of Science"*] , Wolfram Media, 2002.

*Wikimedia Foundation.
2010.*