ONE DIMENSIONAL nARY DENSITY CLASSIFICATION USING TWO CELLULAR AUTOMATON RULES

Suppose each site on a one-dimensional chain with periodic boundary condition may take on any one of the states 0,1,…,n-1; can you find out the most frequently occurring state using cellular automaton? Here, we prove that while the above density classification task cannot be resolved by a single cellular automaton, this task can be performed efficiently by applying two cellular automaton rules in succession.