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.

arXiv commentRevtex, 4 pages, final version accepted by Phys.Rev.E

References in corpus (4)

• Solution of the Density Classification Problem with Two Cellular Automata Rules
• A Possible Nanometer-scale Computing Device Based on an Adding Cellular Automaton
• One Dimensional $n$ary Density Classification Using Two Cellular Automaton Rules
• Classifying Rational Densities Using Two One-Dimensional Cellular Automata

Cited by in corpus (5)

• A comparison of evaluation methods in coevolution
• Solving the Parity Problem with Rule 60 in Array Size of the Power of Two
• Modulo Three Problem With A Cellular Automaton Solution
• On the Parity Problem in One-Dimensional Cellular Automata
• Finding The Sign Of A Function Value By Binary Cellular Automaton