Evaluation of Update Rules for Parity Checking by Asynchronous Cellular Automata

Abstract

We investigate novel aspects of asynchronous Cellular Automata (CA) in a broad scope of rule variants for solving the parity problem. Given a one-dimensional binary vector, the task is to determine whether the parity over all bits is even or odd. Therefore, the convergence of an update process is studied with local updates on 2-, 3- or 4-bit neighborhood pattern following a uniform, parity preserving rule. We assume asynchronous random updates according to a Markov process, which is evaluated via simulation and analytical means. We compare and optimize rule variants regarding their convergence to two different final states, which indicate even versus odd parity. Beyond the all-one and all-zero configurations, we widen the scope to other final states and we include acyclic rule applications, which lead to promising convergence properties.