Efficient Solutions of the Density Classification Task in One-Dimensional Cellular Automata: Where Can They Be Found?

Abstract

The density classification task is one among other benchmark problems for studying the ability of cellular automata to solve problems through emergent collective computations. The density classification task attempts to find a local rule that can perform majority voting in an arbitrary initial configuration of a cellular automaton. Solutions for this problem were designed by means of several training mechanisms, more particularly optimization algorithms, due to the lack of standard procedures for selecting suitable local rules. In this paper, we propose new investigations into density determination in one-dimensional cellular automata of radius r = 4. We show that our proposal allows retaining a considerable number of unknown rules, some of which may outperform the current efficient solutions. Moreover, we give explanations about the computational mechanisms making global computations emerge so that the considered problem is solved. This is a key element for improving both the general understanding of the way in which computational tasks are solved by emergence and the selection of suitable local state-transitions rules.