Skip to main content
Shift-Symmetric Configurations in Two-Dimensional Cellular Automata: Irreversibility, Insolvability, and Enumeration
Mathematics and Statistics Faculty Publications and Presentations
  • Peter Banda, University of Luxembourg
  • John S. Caughman, IV, Portland State University
  • Martin Cenek, University of Alaska, Anchorage
  • Christof Teuscher, Portland State University
Document Type
Publication Date
  • 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.


The views expressed are those of the author(s) and do not reflect the official policy or position of the Department of Defense or the U.S. Government. Approved for Public Release, Distribution Unlimited.

Persistent Identifier
Citation Information
Peter Banda, John S. Caughman, Martin Cenek and Christof Teuscher. "Shift-Symmetric Configurations in Two-Dimensional Cellular Automata: Irreversibility, Insolvability, and Enumeration" (2017)
Available at: