Parity Problem With A Cellular Automaton Solution
<|reference_start|>Parity Problem With A Cellular Automaton Solution: 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.<|reference_end|>
@article{lee2001parity,
    title={Parity Problem With A Cellular Automaton Solution},
    author={K. M. Lee, Hao Xu and H. F. Chau},
    journal={arXiv preprint arXiv:nlin/0102026},
    year={2001},
    doi={10.1103/PhysRevE.64.026702},
    archivePrefix={arXiv},
    eprint={nlin/0102026},
    primaryClass={nlin.CG cond-mat.stat-mech cs.CC nlin.AO}
}