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.

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 }$.

...
Wikipedia