Shift-symmetric configurations in two-dimensional cellular automata: irreversibility, insolvability, and enumeration
From MaRDI portal
Publication:5227589
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.
Recommendations
Cites work
- scientific article; zbMATH DE number 3761989 (Why is no real title available?)
- scientific article; zbMATH DE number 3338162 (Why is no real title available?)
- scientific article; zbMATH DE number 960162 (Why is no real title available?)
- scientific article; zbMATH DE number 2229245 (Why is no real title available?)
- A low-cost high-capacity associative memory design using cellular automata
- A novel image encryption algorithm using chaos and reversible cellular automata
- Algebraic properties of cellular automata
- Cellular automata and finite groups
- Cellular automata and groups
- Cellular automata for image resizing
- Cellular automaton model of crowd evacuation inspired by slime mould
- Computation theoretic aspects of cellular automata
- Conservative logic
- Counting toroidal binary arrays
- Discrete DNA Reaction-Diffusion Model for Implementing Simple Cellular Automaton
- Encyclopedia of Complexity and Systems Science
- Engineering Self-Organising Systems
- Evolutionary Cellular Automata Based-Approach for Edge Detection
- Group colorings and Bernoulli subflows
- IV. Spirometric studies of Yemenite and Kurdish Jews in Israel
- On DNA-based gellular automata
- On the generation of high-quality random numbers by two-dimensional cellular automata
- Periodic forests of stunted trees
- Reversibility of 2D cellular automata is undecidable
- Simple Computation-Universal Cellular Spaces
- Statistical mechanics of cellular automata
- Symmetry in self-correcting cellular automata
- The Garden-of-Eden Theorem for Finite Configurations
- The Role of Conceptual Structure in Designing Cellular Automata to Perform Collective Computation
- The attractor-basin portrait of a cellular automaton
- Turbulent pattern bases for cellular automata
- Two-dimensional cellular automata
- Two-dimensional cellular automata of radius one for density classification task
- Very effective evolutionary techniques for searching cellular automata rule spaces
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)
