Tag Archives: 2D

Shift-symmetric configurations in two-dimensional cellular automata: Irreversibility, insolvability, and enumeration

Now available online: P. Banda, J. Caughman, M. Cenek, C. Teuscher, “Shift-symmetric configurations in two-dimensional cellular automata: Irreversibility, insolvability, and enumeration,” Chaos 29, 063120 (2019), https://doi.org/10.1063/1.5089889

 
Symmetry is a synonym for beauty and rarity, and generally perceived as something desired. In this paper, we investigate an opposing side of symmetry and show how it can irreversibly “corrupt” a computation, and restrict a system’s dynamics and its potentiality. We demonstrate this fundamental phenomenon, which we call “configuration shift-symmetry,” affecting many crucial distributed tasks on the simplest gridlike synchronous system of cellular automation. We show how to count these symmetric inputs depending on a lattice size and its prime factorization, how likely they are encountered, and how to detect them.

New Chaos Paper

Our new paper is is accepted in the Chaos journal: P. Banda, J. Caughman, M. Cenek, C. Teuscher, “Shift-Symmetric Configurations in Two-Dimensional Cellular Automata: Irreversibility, Insolvability, and Enumeration.”

Abstract: 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.