Shift-symmetric configurations in two-dimensional cellular automata: Irreversibility, insolvability, and enumeration
From MaRDI portal
Publication:5227589
DOI10.1063/1.5089889zbMATH Open1416.37015arXiv1703.09030OpenAlexW2617486868WikidataQ91559800 ScholiaQ91559800MaRDI QIDQ5227589FDOQ5227589
Martin Cenek, Peter Banda, John S. IV Caughman, Christof Teuscher
Publication date: 6 August 2019
Published in: Chaos: An Interdisciplinary Journal of Nonlinear Science (Search for Journal in Brave)
Abstract: 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.
Full work available at URL: https://arxiv.org/abs/1703.09030
Recommendations
Cites Work
- Conservative logic
- Very effective evolutionary techniques for searching cellular automata rule spaces
- Statistical mechanics of cellular automata
- Title not available (Why is that?)
- Title not available (Why is that?)
- Group Colorings and Bernoulli Subflows
- On DNA-Based Gellular Automata
- Title not available (Why is that?)
- Simple Computation-Universal Cellular Spaces
- Encyclopedia of Complexity and Systems Science
- Cellular Automata and Groups
- A novel image encryption algorithm using chaos and reversible cellular automata
- Computation theoretic aspects of cellular automata
- Algebraic properties of cellular automata
- Symmetry in self-correcting cellular automata
- Reversibility of 2D cellular automata is undecidable
- Two-dimensional cellular automata
- The attractor-basin portrait of a cellular automaton
- The Garden-of-Eden Theorem for Finite Configurations
- Cellular Automata for Image Resizing
- Periodic forests of stunted trees
- On the generation of high-quality random numbers by two-dimensional cellular automata
- Turbulent pattern bases for cellular automata
- IV. Spirometric studies of Yemenite and Kurdish Jews in Israel
- Cellular automata and finite groups
- Engineering Self-Organising Systems
- Two-dimensional cellular automata of radius one for density classification task
- Discrete DNA Reaction-Diffusion Model for Implementing Simple Cellular Automaton
- Cellular automaton model of crowd evacuation inspired by slime mould
- Counting toroidal binary arrays
- Evolutionary Cellular Automata Based-Approach for Edge Detection
- Title not available (Why is that?)
- The Role of Conceptual Structure in Designing Cellular Automata to Perform Collective Computation
- A low-cost high-capacity associative memory design using cellular automata
This page was built for publication: Shift-symmetric configurations in two-dimensional cellular automata: Irreversibility, insolvability, and enumeration
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5227589)
