SOLUTION OF THE DENSITY CLASSIFICATION PROBLEM WITH 2 CELLULAR-AUTOMATA RULES

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.