Density Classification Quality of the Traffic-majority Rules

Abstract

The density classification task is a famous problem in the theory of cellular automata. It is unsolvable for deterministic automata, but recently solutions for stochastic cellular automata have been found. One of them is a set of stochastic transition rules depending on a parameter $\eta$, the traffic-majority rules. Here I derive a simplified model for these cellular automata. It is valid for a subset of the initial configurations and uses random walks and generating functions. I compare its prediction with computer simulations and show that it expresses recognition quality and time correctly for a large range of $\eta$ values.

40 pages, 9 figures. Accepted by the Journal of Cellular Automata. (Some typos corrected; the numbers for theorems, lemmas and definitions have changed with respect to version 1.)