Tag Archives: insolvability

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.