Computational Evidence Against the Possibility of Density Determination with Fixed Arrangements of Non-Local Elementary Rules
Pedro P.B. De Oliveira, Fernando Faria, Rogério Zanon and Renato M. Leite
Cellular automata with alternative definitions to the standard enable different ways of processing global computational tasks based on local actions. Here, we evaluate the existence of non-uniform arrangements of elementary cellular automata, fixed in their corresponding cells, in the resolution of the classical density classification problem, namely, the determination of the predominant bit in a cyclic binary string. Variations in the pattern of neighbourhood connections are studied in different rule arrangements by means of non-local connections, and solutions are sought exhaustively for lattice size N = 5, enumeratively for N = 7, and with evolutionary searches for N ∈ {7, 9, 11}. We rely on non-local neighbourhoods as a way to extend the rule space beyond the elementary. Perfect solutions were found only for N = 5, but no generalisation was possible for N = 7. Overall, all maximally performing rule arrangements found turn out to require at least one rule with global ou nearly global action. The joint outcome of the computational experiments contributes to the general, still open question of whether it is possible to solve density classification with fixed, non-uniform rule arrangements, by suggesting a negative possibility.
Keywords: Elementary cellular automata, density classification task, DCT, emergent computation, non-uniform, non-local, hybrid, evolutionary search, genetic algorithm