An Effective Approach for Solving the Density Classification Task by Cellular Automata
Zakaria Laboudi · 2019
The density classification or density determination is one among other ongoing problems for studying the abilities of cellular automata to avail themselves of emergent collective computations to solve computational problems. For this task, it is requested to design rules in order to perform the majority voting in an arbitrary initial configuration of a cellular automaton, using local interactions. Several solutions were designed by means of diverse training mechanisms, especially optimization algorithms. This is due to the lack of clear understanding of the nature of computations carried out by cellular automata and therefore the absence of a standard process for writing appropriate state-transition rules. Hence, we propose a novel approach for density determination using cellular automata of neighborhood's radius r=4. Then, we show that our proposal allows retaining new unknown rules that outperform the current efficient ones, in addition to all previously existing solutions. Also, we provide explanations about the mechanisms leading computations to emerge so as to solve the considered task. This is a key element that serves to enhance our knowledge about the way in which cellular automata solve computational tasks by emergence.