An Exact Solution to the Two-Dimensional Arbitrary-Threshold Density Classification Problem
Sami Torbey and Selim G. Akl
Density classification is one of the most studied cellular automata problems. As initially presented [5], it does not have an exact solution [7]. However, [2] and [4] demonstrate that a simple change in the proposed accepting condition makes such a solution easily achievable for one-dimensional cellular automata. We show not only that a similar result is possible for two-dimensional cellular automata, but also that this result can be obtained in O(√n) expected running time (where n is the total number of cells in the automaton), compared to an O(n) running time for the one-dimensional case – thus answering an open problem presented in [1]. Our proposed automaton is also capable of classifying arbitrary density thresholds (not just ½).
Keywords: Cellular automata, arbitrary density classification, majority, two dimensions, rule 184, gravity.