Computational Mechanisms for Solving the Density Classification Task by Cellular Automata
Zakaria Laboudi and Salim Chikhi
The density classification task is one of the most adopted benchmark problems to study computational abilities of cellular automata. It consists in designing a cellular automaton that converges to uniform configurations according to the most frequent state in initial configurations. Earlier solutions for this task were designed by different methods and techniques; but since the symmetry and the number-conserving properties were introduced, many unknown solutions were found. In this work, we are interested in analyzing and understanding the general mechanisms by which cellular automata perform decentralized emergent computations to solve that task. For this purpose, we firstly propose a regular structure for the space of symmetric number-conserving cellular automata rules of radius r = 3. This allows us to outline their supported low-level computations. We show then that the proposed structure can significantly help to analyze the different solutions and, to make comparisons and conceptual connections among them. It also allows giving explanations about the computational strategies used by the currently best-known solutions. Consequently, we could design new higher performing solutions – as compared to the currently best-known ones – using cellular automata of radius r = 4.
Keywords: Complex systems, emergent computation, cellular automata, density classification task, number-conserving property, symmetry property