Computer Engineering Commons^™

Shift-Symmetric Configurations In Two-Dimensional Cellular Automata: Irreversibility, Insolvability, And Enumeration, Peter Banda, John S. Caughman Iv, Martin Cenek, Christof Teuscher

Mathematics and Statistics Faculty Publications and Presentations

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 …