Density classification performance of the Gacs-Kurdyumov-Levin four-states cellular automaton model IV and related automata

Almost four decades ago (in 1978), Gacs, Kurdyumov, and Levin (GKL) introduced three different cellular automata (CA), which they called models II, IV, and VI, to investigate whether nonequilibrium interacting particle systems are capable of displaying phase transitions. Their objective was to examine the ``positive probabilities conjecture,'' according to which one-dimensional particle systems with short-range interactions and positive transition probabilities are always ergodic. This conjecture has been disproved---much to the awe of the practicing community---many times since then, with the introduction of several models that have become archetypal models in theoretical computer science and nonequilibrium statistical mechanics.

As a by-product of their investigations, GKL introduced the density classification problem in the cellular automata literature. The density classification task consists in classifying arrays of symbols according to their initial density of symbols using local rules, and is completed successfully if a correct verdict as to which was the initial majority state is obtained in time at most linear in the size of the input array. Density classification is a nontrivial task for CA in which cells interact over finite neighbourhoods, because then the cells have to achieve a global consensus cooperating locally only. Ultimately, that means that information should flow through the entire system, be processed by the cells, and be not destroyed or become incoherent in the process---entropy must loose to work in the task, a relevant property in the theoretical analysis of data processing and storage under noise. For one-dimensional locally interacting systems of autonomous and memoryless cells, emergence of collective behavior is required in these cases. In this context, GKL model II has been extensively scrutinized as a model system related with the concepts of emergence, communication, efficiency, and connectivity. The other two GKL models, however, did not receive much attention.

Here we characterize the density classification performance of Gacs, Kurdyumov, and Levin's ``model~IV,'' a four-states cellular automaton with three absorbing states, by Monte Carlo simulations. We show that model~IV compares well with its sibling model~II in the density classification task, the additional states being barely relevant for its performance. We also investigate the performance of model~IV under the influence of noise and show that it cannot perform the density classification task reliably at any nonzero level of noise, an indication that, most probably, it becomes ergodic in this case.