Shift-Symmetric Configurations in Two-Dimensional Cellular Automata: Irreversibility, Insolvability, and EnumerationMathematics and Statistics Faculty Publications and Presentations
SponsorThis material is based upon work supported by the National Science Foundation under grants #1028120, #1028378, #1518833, and by the Defense Advanced Research Projects Agency (DARPA) under award #HR0011-13-2-0015.
- Cellular automata,
- Symmetry -- Effect on computational processes,
- Symmetry -- Identification,
- Distributed systems
AbstractThe search for symmetry as an unusual yet profoundly appealing phenomenon, and the origin of regular, repeating configuration patterns have been for a long time a central focus of complexity science, and physics. Here, we introduce group-theoretic concepts to identify and enumerate the symmetric inputs, which result in irreversible system behaviors with undesired effects on many computational tasks. The concept of so-called configuration shift-symmetry is applied on two-dimensional cellular automata as an ideal model of computation. The results show the universal insolvability of “non-symmetric” tasks regardless of the transition function. By using a compact enumeration formula and bounding the number of shift-symmetric configurations for a given lattice size, we efficiently calculate how likely a configuration randomly generated from a uniform or density-uniform distribution turns shift-symmetric. Further, we devise an algorithm detecting the presence of shift-symmetry in a configuration. The enumeration and probability formulas can directly help to lower the minimal expected error for many crucial (non-symmetric) distributed problems, such as leader election, edge detection, pattern recognition, convex hull/minimum bounding rectangle, and encryption. Besides cellular automata, the shift-symmetry analysis can be used to study the non-linear behavior in various synchronous rule-based systems that include inference engines, Boolean networks, neural networks, and systolic arrays.
Citation InformationPeter Banda, John S. Caughman, Martin Cenek and Christof Teuscher. "Shift-Symmetric Configurations in Two-Dimensional Cellular Automata: Irreversibility, Insolvability, and Enumeration" (2017)
Available at: http://works.bepress.com/christof-teuscher/26/