H. Fuks, SOLUTION OF THE DENSITY CLASSIFICATION PROBLEM WITH 2 CELLULAR-AUTOMATA RULES, Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topics, 55(3), 1997, pp. 2081-2084
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 con
structed. We show that a pair of elementary rules, namely the ''traffi
c rule'' 184 and the ''majority rule'' 232, performs the task perfectl
y. This solution employs the second order phase transition between the
freely moving phase and the jammed phase occurring in rule 184. We pr
esent exact calculations of the order parameter in this transition usi
ng the method of preimage counting.