On Density Determination With Cellular Automata: Results, Constructions and Directions
Pedro P.B. De Oliveira
The attempt to determine which is the most frequent cell state in an arbitrary initial configuration of a cellular automaton is quite likely the most well-studied benchmark problem in the context of computational ability of cellular automata. In its standard form, the problem is formulated in terms of a binary cellular automaton, whose action on a finite, one-dimensional lattice, with arbitrary odd-sized length and periodic boundary, would converge to a quiescent configuration of 1s or 0s, according to the respective prevailing bit in the initial configuration. Although extremely simple in formulation, the problem has unveiled a rich web of conceptual connections, which, at the same time, have enlarged and challenged our understanding about how to perform computations within cellular automata. In spite of the fact that the problem as such is knowingly impossible to solve, many proposals have been made in attempting to solve it, perfectly or not, in a variety of forms and generalisations. Here, we summarise the negative results in the context, and survey the main proposals with larger dimensions; higher number of states; fixed boundary conditions; infinite size lattices; asynchronous update schemes; rule changing throughout the temporal evolution; non-uniform cellular automata; memory addition to the rules; and stochastic rules. We also discuss burdens that would need to be overcome in the attempt to characterise the best possible imperfect solution in the standard formulation. The resulting picture clarifies what is known so far about the problem, and what is left to further investigation.
Keywords: Density classification task, DCT, majority problem, emergent computation, cellular automata, conservative rule.