This 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
The 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.
Banda, Peter; Caughman, John S. IV; Cenek, Martin; and Teuscher, Christof, "Shift-Symmetric Configurations in Two-Dimensional Cellular Automata: Irreversibility, Insolvability, and Enumeration" (2017). Mathematics and Statistics Faculty Publications and Presentations. 169.