Solution of the Density Classification Problem with Two Cellular Automata Rules

Abstract

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.

4 pages (RevTeX), 1 figure

Cited by in corpus (28)

• Exact solution of a cellular automaton for traffic
• A Survey of Cellular Automata: Types, Dynamics, Non-uniformity and Applications
• Non-deterministic density classification with diffusive probabilistic cellular automata
• Exact results for deterministic cellular automata traffic models
• Fitness landscape of the cellular automata majority problem: View from the Olympus
• A class of cellular automata equivalent to deterministic particle systems
• Parity Problem With A Cellular Automaton Solution
• Convergence to equilibrium in a class of interacting particle systems evolving in discrete time
• One Dimensional $n$ary Density Classification Using Two Cellular Automaton Rules
• An extinction-survival-type phase transition in the probabilistic cellular automaton p182-q200
• Solutions on 1D and 2D Density Classification Problem Using Programmable Cellular Automata
• Signatures of a quantum stabilized fluctuating phase and critical dynamics in a kinetically-constrained open many-body system with two absorbing states
• Sensitivity to noise and ergodicity of an assembly line of cellular automata that classifies density
• Quantum cellular automata for quantum error correction and density classification
• Classifying Rational Densities Using Two One-Dimensional Cellular Automata
• Strictly local one-dimensional topological quantum error correction with symmetry-constrained cellular automata
• The Clouds in Asynchronous Cellular Automata
• Explorations of ternary cellular automata and ternary density classification problems
• Approximating dynamics of a number-conserving cellular automaton by a finite-dimensional dynamical system
• Density Classification with Non-Unitary Quantum Cellular Automata
• On the Parity Problem in One-Dimensional Cellular Automata
• Density classification performance and ergodicity of the Gacs-Kurdyumov-Levin cellular automaton model IV
• Structure and dynamics in the low-density phase of a two-dimensional cellular automaton model of traffic flow
• Dynamics of the Cellular Automaton Rule 142
• Simply modified GKL density classifiers that reach consensus faster
• Deterministic Computing Mechanism for Perfect Density Classification
• First-passage processes in a deterministic one-dimensional cellular automaton model of traffic flow
• Finding The Sign Of A Function Value By Binary Cellular Automaton