Thus, this problem is an important test case in measuring the computational power of cellular automaton systems.
; a correct solution to the voting problem must eventually set all cells to zero if
Gács, Kurdyumov, and Levin found an automaton that, although it does not always solve the majority problem correctly, does so in many cases.
[1] In their approach to the problem, the quality of a cellular automaton rule is measured by the fraction of the
The rule proposed by Gacs, Kurdyumov, and Levin sets the state of each cell as follows.
In randomly generated instances, this achieves about 78% accuracy in correctly determining the majority.
Das, Mitchell, and Crutchfield showed that it is possible to develop better rules using genetic algorithms.
[2] In 1995, Land and Belew[3] showed that no two-state rule with radius r and density ρ correctly solves the voting problem on all starting configurations when the number of cells is sufficiently large (larger than about 4r/ρ).
They then show that any assumed perfect rule will either cause an isolated one that pushed the ratio over
In 2013, Busic, Fatès, Marcovici and Mairesse gave a simpler proof of the impossibility to have a perfect density classifier, which holds both for deterministic and stochastic cellular and for any dimension.
In particular, for the Rule 184 automaton, when run on a finite universe with cyclic boundary conditions, each cell will infinitely often remain in the majority state for two consecutive steps while only finitely many times being in the minority state for two consecutive steps.
That last property is quite unique in the sense that it associates a condition on the form of the rule to a global behaviour.