A full computation-relevant topological dynamics classification of elementary cellular automata
From MaRDI portal
Publication:2944652
DOI10.1063/1.4771662zbMATH Open1319.37008arXiv1107.2080OpenAlexW3100265383WikidataQ51282189 ScholiaQ51282189MaRDI QIDQ2944652FDOQ2944652
Publication date: 2 September 2015
Published in: Chaos: An Interdisciplinary Journal of Nonlinear Science (Search for Journal in Brave)
Abstract: Cellular automata are both computational and dynamical systems. We give a complete classification of the dynamic behaviour of elementary cellular automata (ECA) in terms of fundamental dynamic system notions such as sensitivity and chaoticity. The "complex" ECA emerge to be sensitive, but not chaotic and not eventually weakly periodic. Based on this classification, we conjecture that elementary cellular automata capable of carrying out complex computations, such as needed for Turing-universality, are at the "edge of chaos".
Full work available at URL: https://arxiv.org/abs/1107.2080
Recommendations
Cites Work
- Title not available (Why is that?)
- Endomorphisms and automorphisms of the shift dynamical system
- Some properties of cellular automata with equicontinuity points
- Classes of linear automata
- Title not available (Why is that?)
- Languages, equicontinuity and attractors in cellular automata
- Title not available (Why is that?)
- Title not available (Why is that?)
- Statistical mechanics of cellular automata
- Title not available (Why is that?)
- Investigating topological chaos by elementary cellular automata dynamics
- Algebraic properties of cellular automata
- A NONLINEAR DYNAMICS PERSPECTIVE OF WOLFRAM'S NEW KIND OF SCIENCE PART I: THRESHOLD OF COMPLEXITY
- Complexity of dynamics as variability of predictability
- On the relationship between Boolean and fuzzy cellular automata
Cited In (19)
- A tutorial on elementary cellular automata with fully asynchronous updating. General properties and convergence dynamics
- Designing complex dynamics in cellular automata with memory
- Progress, gaps and obstacles in the classification of cellular automata
- On the Reversibility of ECAs with Fully Asynchronous Updating: The Recurrence Point of View
- Unraveling simplicity in elementary cellular automata
- A complete and efficiently computable topological classification of D-dimensional linear cellular automata over \(Z_{m}\)
- Title not available (Why is that?)
- Classification of cellular automata based on the Hamming distance
- A Study of Chaos in Cellular Automata
- An information-based classification of elementary cellular automata
- A simple digital spiking neural network: synchronization and spike-train approximation
- A comprehensive taxonomy of cellular automata
- Topological chaos of universal elementary cellular automata rule
- Classifying 1D elementary cellular automata with the 0-1 test for chaos
- New aspects of symmetry of elementary cellular automata
- A complete and efficiently computable topological classification of D-dimensional linear cellular automata over Z m
- Permutation binary neural networks: analysis of periodic orbits and its applications
- Shift-equivalence of \(k\)-ary, one-dimensional cellular automata rules
- A study of chaos in non-uniform cellular automata
This page was built for publication: A full computation-relevant topological dynamics classification of elementary cellular automata
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2944652)
