Parity problem with a cellular automaton solution.
The parity of a bit string of length N is a global quantity that can be efficiently computed 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(N2) time.
Lee
K M
KM
Department of Physics, University of Hong Kong, Pokfulam Road, Hong Kong.
Xu
H
H
Chau
H F
HF