Solution of the Density Classification Problem with Two Cellular Automata Rules

Details Solution of the Density Classification Problem with Two Cellular Automata Rules Solution of the Density Classification Problem with Two Cellular Automata Rules

1997-03-07

arxiv.org/abs/comp-gas/9703001v1

Phys. Rev. E 55, 2081R (1997)

Nonlinear Sciences

Cellular Automata and Lattice Gases

4 pages (RevTeX), 1 figure

Scientific paper

10.1103/PhysRevE.55.R2081

Recently, Land and Belew [Phys. Rev. Lett. 74, 5148 (1995)] have shown that no one-dimensional two-state cellular automaton which classifies binary strings according to their densities of 1's and 0's can be constructed. We show that a pair of elementary rules, namely the ``traffic rule'' 184 and the ``majority rule'' 232, performs the task perfectly. This solution employs the second order phase transition between the freely moving phase and the jammed phase occurring in rule 184. We present exact calculations of the order parameter in this transition using the method of preimage counting.

Affiliated with

Also associated with

No associations

Rating

Solution of the Density Classification Problem with Two Cellular Automata Rules does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Solution of the Density Classification Problem with Two Cellular Automata Rules, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Solution of the Density Classification Problem with Two Cellular Automata Rules will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-188427