Majority problem

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 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. 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  \rho ; a correct solution to the voting problem must eventually set all cells to zero if \tfrac{i}{i+j} and must eventually set all cells to one if \tfrac{j}{i+j} > \rho . The desired eventual state is unspecified if \tfrac{j}{i+j} = \rho . ==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 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. 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). ==Necessary Conditions for a perfect density classifying cellular Automata== Given that the task had moved from impossible to rather simple depending on the definition of the desired output, the problem was generalised to the following definition: a perfect density classifying automaton is simply defined as an automaton where the set of configurations reachable when the density of the starting configuration is below the threshold is perfectly disjoint with the set of configurations reachable when the density of the starting configuration is above the threshold. Using That definition Capcarrere and Sipper were able to prove two necessary conditions for a celullar automaton to be a perfect density classifyer: (1) the density of the initial configuration must be conserved over time, and (2) the rule table must exhibit a density of 0.5 (even when the threshold for classification is different from 0.5). That last property is quite unique in the sense that it associates a condition on the form of the rule to a global behaviour.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1313963151 under CC BY-SA 4.0; modifications have been made.