Majority problem (cellular automaton)

The majority problem, or density classification task, is the problem of finding one-dimensional cellular automaton rules that accurately perform majority voting.

Using local transition rules, cells cannot know the total count of all the ones in system. In order to count the number of ones (or, by symmetry, the number of zeros), the system requires a logarithmic number of bits in the total size of the system. It also requires the system send messages over a distance linear in the size of the system and for the system to recognize a non-regular language. Thus, this problem is an important test case in measuring the computational power of cellular automaton systems.

Problem statement

Given a configuration of a two-state cellular automaton with i + j cells total, i of which are in the zero state and j of which are in the one state, a correct solution to the voting problem must eventually set all cells to zero if i > j and must eventually set all cells to one if i < j. The desired eventual state is unspecified if i = j.

The problem can also be generalized to testing whether the proportion of zeros and ones is above or below some threshold other than 50%. In this generalization, one is also given a threshold ${\displaystyle \rho }$; a correct solution to the voting problem must eventually set all cells to zero if ${\displaystyle {\tfrac {i}{i+j}}<\rho }$ and must eventually set all cells to one if ${\displaystyle {\tfrac {j}{i+j}}>\rho }$. The desired eventual state is unspecified if ${\displaystyle {\tfrac {j}{i+j}}=\rho }$.

Approximate solutions

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 ${\displaystyle 2^{i+j}}$ possible starting configurations that it correctly classifies.

The rule proposed by Gacs, Kurdyumov, and Levin sets the state of each cell as follows. If a cell is 0, its next state is formed as the majority among the values of itself, its immediate neighbor to the left, and its neighbor three spaces to the left. If, on the other hand, a cell is 1, its next state is formed symmetrically, as the majority among the values of itself, its immediate neighbor to the right, and its neighbor three spaces to the right. 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]

Impossibility of a perfect classifier

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/ρ).

Their argument shows that because the system is deterministic, every cell surrounded entirely by zeros or ones must then become a zero. Likewise, any perfect rule can never make the ratio of ones go above ${\displaystyle \rho }$ if it was below (or vice versa). They then show that any assumed perfect rule will either cause an isolated one that pushed the ratio over ${\displaystyle \rho }$ to be cancelled out or, if the ratio of ones is less than ${\displaystyle \rho }$, will cause an isolated one to introduce spurious ones into a block of zeros causing the ratio of ones to be become greater than ${\displaystyle \rho }$.

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[4].

Exact solution with alternative termination conditions

As observed by Capcarrere, Sipper, and Tomassini,[5][6] the majority problem may be solved perfectly if one relaxes the definition by which the automaton is said to have recognized the majority. 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.

Alternatively, a hybrid automaton that runs Rule 184 for a number of steps linear in the size of the array, and then switches to the majority rule (Rule 232), that sets each cell to the majority of itself and its neighbors, solves the majority problem with the standard recognition criterion of either all zeros or all ones in the final state. However, this machine is not itself a cellular automaton.[7] Moreover, it has been shown that Fukś's composite rule is very sensitive to noise and cannot outperform the noisy Gacs-Kurdyumov-Levin automaton, an imperfect classifier, for any level of noise (e.g., from the environment or from dynamical mistakes).[8]

References

1. Gács, Péter; Kurdyumov, G. L.; Levin, L. A. (1978). "One dimensional uniform arrays that wash out finite islands". Problemy Peredachi Informatsii (in Russian). 14: 92–98.
2. Das, Rajarshi; Crutchfield, J. P.; Mitchell, Melanie; Hanson, J. E. (1995). Eshelman, Larry J. (ed.). Evolving globally synchronized cellular automata (PDF). Proceedings of the Sixth International Conference on Genetic Algorithms. San Francisco: Morgan Kaufmann.
3. Land, Mark; Belew, Richard (1995). "No perfect two-state cellular automata for density classification exists". Physical Review Letters. 74 (25): 1548–1550. Bibcode:1995PhRvL..74.5148L. doi:10.1103/PhysRevLett.74.5148. PMID 10058695.
4. Bušić, Ana; Fatès, Nazim; Marcovici, Irène; Mairesse, Jean (2013). "Density classification on infinite lattices and trees". Electronic Journal of Probability. 51. doi:10.1214/EJP.v18-2325.
5. Capcarrere, Mathieu S.; Sipper, Moshe; Tomassini, Marco (1996). "Two-state, r = 1 cellular automaton that classifies density". Phys. Rev. Lett. 77 (24): 4969–4971. Bibcode:1996PhRvL..77.4969C. doi:10.1103/PhysRevLett.77.4969. PMID 10062680.
6. Sukumar, N. (1998). "Effect of boundary conditions on cellular automata that classify density". arXiv:comp-gas/9804001. Bibcode:1998comp.gas..4001S. Cite journal requires |journal= (help)
7. Fukś, Henryk (1997). "Solution of the density classification problem with two cellular automata rules". Physical Review E. 55 (3): 2081–2084. arXiv:comp-gas/9703001. Bibcode:1997comp.gas..3001F. doi:10.1103/physreve.55.r2081.
8. Mendonça, J. R. G. (2011). "Sensitivity to noise and ergodicity of an assembly line of cellular automata that classifies density". Physical Review E. 83 (3): 031112. arXiv:1010.0239. Bibcode:2011PhRvE..83c1112M. doi:10.1103/PhysRevE.83.031112.