Affiliations: Department of Mathematics, FI-20014 University of Turku, Turku Finland, jkari@utu.fi | LIFO Bat. 3IA, Université d'Orléans, Rue Léonard de Vinci, B.P. 6759, F-45067 ORLEANS Cedex 2, France, bastien.le-gloannec@univ-orleans.fr
Note: [] Address for correspondence: Department of Mathematics, FI-20014 University of Turku, Finland Research supported by the Academy of Finland Grant 131558
Abstract: The density classification task asks to design a cellular automaton that converges to the uniform configuration that corresponds to the state that is in majority in the initial configuration. We investigate connections of this problem to state-conserving cellular automata. We propose a modified traffic CA that washes out finite islands in the same way as the Gacs, Kurdyumov and Levin automaton, but is also guaranteed to converge to a uniform configuration on rings of odd size. We find experimentally several good classifiers that are close to state-conserving cellular automata, and we observe that the best performing known density classifier by Wolz and de Oliveira is only a simple swap away from a state-conserving automaton.
Keywords: Cellular automata, density classification, traffic CA
