Majority problem (cellular automaton)
Encyclopedia
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.
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
; 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 
.
found an automaton that, although it does not always solve the majority problem correctly, does so in many cases. In their approach to the problem,
the quality of a cellular automaton rule is measured by the fraction of the
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 algorithm
s.
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 
.
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.
Cellular automaton
A cellular automaton is a discrete model studied in computability theory, mathematics, physics, complexity science, theoretical biology and microstructure modeling. It consists of a regular grid of cells, each in one of a finite number of states, such as "On" and "Off"...
rules that accurately perform majority voting
Majority function
In Boolean logic, the majority function is a function from n inputs to one output. The value of the operation is false when n/2 or more arguments are false, and true otherwise....
.
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
Regular language
In theoretical computer science and formal language theory, a regular language is a formal language that can be expressed using regular expression....
. 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 automata 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
; 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 .Approximate solutions
Gács, Kurdyumov, and LevinLeonid Levin
-External links:* at Boston University....
found an automaton that, although it does not always solve the majority problem correctly, does so in many cases. In their approach to the problem,
the quality of a cellular automaton rule is measured by the fraction of the
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
Melanie Mitchell
Melanie Mitchell is a professor of computer science at Portland State University. She has worked at the Santa Fe Institute and Los Alamos National Laboratory...
, and Crutchfield showed that it is possible to develop better rules using genetic algorithm
Genetic algorithm
A genetic algorithm is a search heuristic that mimics the process of natural evolution. This heuristic is routinely used to generate useful solutions to optimization and search problems...
s.
Impossibility of a perfect classifier
In 1994, Land and Belew 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
Deterministic algorithm
In computer science, a deterministic algorithm is an algorithm which, in informal terms, behaves predictably. Given a particular input, it will always produce the same output, and the underlying machine will always pass through the same sequence of states...
, 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 .Exact solution with alternative termination conditions
As observed by Capcarrere, Sipper, and Tomassini, 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 184Rule 184
Rule 184 is a one-dimensional binary cellular automaton rule, notable for solving the majority problem as well as for its ability to simultaneously describe several, seemingly quite different, particle systems:...
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.