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

• We solve the density classification problem.
• This is one of the most studied inverse problems in cellular automata.
• We solve this problem with a CA inspired by two mechanisms that are ubiquitous in nature.
• These mechanisms are diffusion and nonlinear sigmoidal response.
• Our solution works in any dimension, for an arbitrary number of cells, and any critical density.

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.