Density Classification Quality of the Traffic-majority Rules
Markus Redeker · arXiv (Cornell University) · 2014
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 $η$, 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 $η$ values.