The Effect of Noise on the Density Classification Task for Various Cellular Automata Rules.

Cellular automata (CA) are discrete dynamical systems with a prominent place in the history and study of artificial life. Here, we focus on the density classification task (DCT) in which a 1-dimensional lattice of Boolean (on/off) automata must perform a form of rudimentary quorum sensing. Typically, the ring lattice consists of 149 cells (though we consider other sizes as well) that update their state according to their own state and its six nearest neighbors in the previous time step. The goal is obtaining Boolean CA rules whose dynamics converges to the majority state of the entire lattice for a given initial configuration of the lattice. This is a nontrivial task because cells have access only to local information, and thus need to integrate and coordinate information across the lattice to converge to the correct collective state. Because initial conditions are random, they have very similar proportions of on and off states, which makes the problem very difficult. This problem has hitherto been studied with the assumption that input to each cell is perfectly stable. Since biological systems that solve similar problems (e.g. bacterial quorum sensing) must operate in noisy environments, here we study the impact of noise on DCT accuracy for the 13 highest-accuracy CA rules from the literature. We use cubewalkers, a recently released GPU-accelerated Boolean simulator to conduct large-scale random experiments. We uncover a trade-off between maximum accuracy without noise and robustness to noise among these high-performance CAs. Moreover, there is no significant difference between rules that were human-designed or evolved computationally.