Reference : Shift-symmetric configurations in two-dimensional cellular automata: Irreversibility,...
Scientific journals : Article
Physical, chemical, mathematical & earth Sciences : Physics
Computational Sciences; Physics and Materials Science
Shift-symmetric configurations in two-dimensional cellular automata: Irreversibility, insolvability, and enumeration
Banda, Peter mailto [University of Luxembourg > Luxembourg Centre for Systems Biomedicine (LCSB) > >]
Caughman, John mailto [Portland State University > Department of Mathematics and Statistics]
Cenek, Martin mailto [University of Portland > Shiley School of Engineering]
Teuscher, Christof mailto [Portland State University > Department of Electrical and Computer Engineering]
AIP Publishing
American Institute of Physics
Yes (verified by ORBilu)
[en] configuration shift-symmetry ; toroidal translation invariance ; two-dimensional cellular automata ; group theory ; pattern formation ; irreversibility ; insolvability ; enumeration ; symmetry detection ; prime factorization ; prime orbit ; mutually-independent generators ; leader election ; spontaneous symmetrization hypothesis
[en] The search for symmetry as an unusual yet profoundly appealing phenomenon, and the origin of regular, repeating configuration patterns have long been a central focus of complexity science and physics. To better grasp and understand symmetry of configurations in decentralized toroidal architectures, we employ group-theoretic methods, which allow us to identify and enumerate these inputs, and argue about irreversible system behaviors with undesired effects on many computational problems. The concept of so-called configuration shift-symmetry is applied to two-dimensional cellular automata as an ideal model of computation. Regardless of the transition function, the results show the universal insolvability of crucial distributed tasks, such as leader election, pattern recognition, hashing, and encryption. By using compact enumeration formulas and bounding the number of shift-symmetric configurations for a given lattice size, we efficiently calculate the probability of a configuration being shift-symmetric for a uniform or density-uniform distribution. Further, we devise an algorithm detecting the presence of shift-symmetry in a configuration.
Given the resource constraints, the enumeration and probability formulas can directly help to lower the minimal expected error and provide recommendations for system’s size and initialization. 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.

File(s) associated to this reference

Fulltext file(s):

Limited access
1.5089889.pdfPublisher postprint686.7 kBRequest a copy

Bookmark and Share SFX Query

All documents in ORBilu are protected by a user license.