Parity problem with a cellular automaton solution
Open Access
- 11 July 2001
- journal article
- research article
- Published by American Physical Society (APS) in Physical Review E
- Vol. 64 (2) , 026702
Abstract
The parity of a bit string of length N is a global quantity that can be efficiently computed using a global counter in 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 binary, uniform, parallel, and deterministic cellular automata applied in succession for a total of time.
Keywords
All Related Versions
This publication has 11 references indexed in Scilit:
- ONE DIMENSIONAL nARY DENSITY CLASSIFICATION USING TWO CELLULAR AUTOMATON RULESInternational Journal of Modern Physics C, 1999
- The emergence of cellular computingComputer, 1999
- Cellular Automata Modeling of Physical Systems1998
- A Simple Cellular Automaton that Solves the Density and Ordering ProblemsInternational Journal of Modern Physics C, 1998
- Computing with cellular automata: Three cases for nonuniformityPhysical Review E, 1998
- A possible nanometer-scale computing device based on an adding cellular automatonApplied Physics Letters, 1997
- Solution of the density classification problem with two cellular automata rulesPhysical Review E, 1997
- Two-state,Cellular Automaton that Classifies DensityPhysical Review Letters, 1996
- No Perfect Two-State Cellular Automata for Density Classification ExistsPhysical Review Letters, 1995
- Statistical mechanics of cellular automataReviews of Modern Physics, 1983