Symmetry in Self-Correcting Cellular Automata
Document Type
Article
Department
Mathematics (HMC)
Publication Date
8-1994
Abstract
We study a class of cellular automata that are capable of correcting finite configurations of errors within a finite amount of time. Subject to certain natural conditions, we determine the geometric symmetries such automata may possess. In three dimensions the answer is particularly simple: such an automaton may be invariant under all proper rotations that leave the underlying lattice invariant, but it cannot be invariant under the inversion that takes each configuration into its mirror image.
Rights Information
© 1994 Academic Press, Inc.
DOI
10.1016/S0022-0000(05)80087-X
Recommended Citation
Nicholas Pippenger, Symmetry in self-correcting cellular automata, Journal of Computer and System Sciences, Volume 49, Issue 1, August 1994, Pages 83-95.
