Classifying Rational Densities Using Two One-Dimensional Cellular Automata

Given a (finite) string of zeros and ones, we report a way to determine if the number of ones is less than, greater than, or equal to a prescribed number by applying two sets of cellular automaton rules in succession. Thus, we solve the general density classification problem using cellular automaton.

H. F. Chau, K. K. Yan, K. Y. Wan, L. W. Siu · 1997