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:
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". 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 of ballistic annihilation, a system of particles moving both leftwards and rightwards through a one-dimensional medium. When two such particles collide, they annihilate 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 associating features of the automaton's state with particles. The name of Rule 184 is a Wolfram code that defines the evolution of its states. The earliest research on Rule 184 is by Li (1987) and Krug & Spohn (1988). In particular, Krug and Spohn already describe all three types of particle system modeled by Rule 184.
Definition A state of the Rule 184 automaton consists of a one-dimensional array of cells, each containing a binary value (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:
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 Wolfram code describing the state table above: the bottom row of the table, 10111000, when viewed as a binary number, is equal to the decimal number 184. The rule set for Rule 184 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 & Spohn (1988) call Rule 184 a deterministic version of a "kinetic Ising 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 a two-way demultiplexer 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 Fredkin gate.
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. Rule 184 and its reflection are the only nontrivial elementary cellular automata to have this property of number conservation. 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. 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. The majority problem 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. The majority problem cannot be solved perfectly if it is required that all cells eventually stabilize to the majority state but the Rule 184 solution avoids this impossibility result by relaxing the criterion by which the automaton recognizes a majority.
… excerpt ends here. Continue reading the full article.
