Rule 184
Rule 184 is a one-dimensional binary cellular automaton rule, notable for solving the majority problem as well as for its ability to simultaneously describe several, seemingly quite different, particle systems: The apparent contradiction between these descriptions is resolved by different ways of associating features of the automaton's state with particles.
[8] 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.
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.
Wang, Kwong & Hui (1998), for instance, state that "the basic cellular automaton model describing a one-dimensional traffic flow problem is rule 184."
Biham, Middleton & Levine (1992) describe a two-dimensional city grid model in which the dynamics of individual lanes of traffic is essentially that of Rule 184.
[16] 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 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.
[17] As shown in the figure, and as originally described by Krug & Spohn (1988),[18] Rule 184 may be used to model deposition of particles onto a surface.
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.
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.
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.
[22] The behavior of certain other systems, such as one-dimensional cyclic cellular automata, can also be described in terms of ballistic annihilation.
Based on this view he describes seven different particles formed by boundaries between regions, and classifies their possible interactions.
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 the context-free language describing strings formed from nested parentheses.
