Parity Problem With A Cellular Automaton Solution

Abstract

The parity of a bit string of length $N$ is a global quantity that can be efficiently compute using a global counter in $O(N)$ time. But is it possible to find the parity using cellular automata with a set of local rule tables without using any global counter? Here, we report a way to solve this problem using a number of $r=1$ binary, uniform, parallel and deterministic cellular automata applied in succession for a total of $O(N^2)$ time.

Revtex, 4 pages, final version accepted by Phys.Rev.E