Solving the density classification problem with a large diffusion and small amplification cellular automaton

Abstract

One of the most studied inverse problems in cellular automata (CAs) is the density classification problem. It consists in finding a CA such that, given any initial configuration of 0s and 1s, it converges to the all- 1 fixed point configuration if the fraction of 1s is greater than the critical density 1/2, and it converges to the all-0 fixed point configuration otherwise. In this paper, we propose an original approach to solve this problem by designing a CA inspired by two mechanisms that are ubiquitous in nature: diffusion and nonlinear sigmoidal response. This CA, which is different from the classical ones because it has many states, has a success ratio of 100%, and works for any system size, any dimension, and any critical density.