Majority problem (cellular automaton)
From Wikipedia, the free encyclopedia
The majority problem, or density classification task, first solved for many configurations by Gács, Kurdyumov, and Levin,[1] 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.
Contents |
[edit] Formal statement of the problem
Given a configuration of a two-state cellular automata with i + j cells total, i of which are in the zero state and j of which are in the one state, and a threshold ρ, a correct solution to the voting problem must eventually set all cells to zero if and must eventually set all cells to one if . The desired eventual state is unspecified if .
We measure the quality of a cellular automaton rule by the fraction of the 2i + j possible starting configurations that it correctly classifies in this way.
[edit] Solutions
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].
[edit] Impossibility of a perfect classifier
In 1994, 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 ρ 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 ρ to be cancelled out or, if the ratio of ones is less than ρ, will cause an isolated one to introduce spurious ones into a block of zeros causing the ratio of ones to be become greater than ρ.
However, as observed by Capcarrere et al.[4][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.
[edit] References
- ^ Gács, Péter; Kurdyumov, G. L.; Levin, L. A. (1978). "One dimensional uniform arrays that wash out finite islands". Problemy Peredachi Informatsii 12: 92–98.
- ^ Das, Rajarshi; Crutchfield, J. P.; Mitchell, Melanie; and Hanson, J. E. (1995). "Evolving globally synchronized cellular automata". Eshelman, Larry J. (ed.) Proceedings of the Sixth International Conference on Genetic Algorithms, San Francisco: Morgan Kaufmann.
- ^ Land, Mark; Belew, Richard (1995). "No perfect two-state cellular automata for density classification exists". Physical Review Letters 74 (25): 1548–1550. doi: .
- ^ Capcarrere, Mathieu S.; Sipper, Moshe; Tomassini, Marco (1996). "Two-state, r = 1 cellular automaton that classifies density". Phys. Rev. Lett. 77: 4969. doi: .
- ^ Fukś, Henryk (1997). "Solution of the density classification problem with two similar cellular automata rules". Physical Review E 55 (3): R2081–R2084. doi: .
- ^ Sukumar, N. (1998). "Effect of boundary conditions on cellular automata that classify density". arXiv:comp-gas/9804001.