Asynchronous Cellular Systems that Solve the Parity Problem

We present stochastic cellular automata that classify the parity of initial conditions. The model is an interacting particles system where cells are updated by pairs, randomly chosen at each time step. A first rule is proposed, with a symmetry between 0’s and 1’s. We show that it classifies the parity of the initial configurations thanks to a non-biased random walk of the frontiers between 0’s and 1’s. We present an analysis of the classification time, as well as numerical simulations, to establish that the classification time scales quadratically with the number of cells. In a second time, breaking the state symmetry, we propose an improvement of this rule with the simultaneous use of two classifying systems.