A full computation-relevant topological dynamics classification of elementary cellular automata
From MaRDI portal
Publication:2944652
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".
Recommendations
Cites work
- scientific article; zbMATH DE number 1818513 (Why is no real title available?)
- scientific article; zbMATH DE number 3888913 (Why is no real title available?)
- scientific article; zbMATH DE number 5595151 (Why is no real title available?)
- scientific article; zbMATH DE number 1257634 (Why is no real title available?)
- scientific article; zbMATH DE number 1963551 (Why is no real title available?)
- A NONLINEAR DYNAMICS PERSPECTIVE OF WOLFRAM'S NEW KIND OF SCIENCE PART I: THRESHOLD OF COMPLEXITY
- Algebraic properties of cellular automata
- Classes of linear automata
- Complexity of dynamics as variability of predictability
- Endomorphisms and automorphisms of the shift dynamical system
- Investigating topological chaos by elementary cellular automata dynamics
- Languages, equicontinuity and attractors in cellular automata
- On the relationship between Boolean and fuzzy cellular automata
- Some properties of cellular automata with equicontinuity points
- Statistical mechanics of cellular automata
Cited in
(28)- Topological conjugacy classification of elementary cellular automata with majority memory
- A complete and efficiently computable topological classification of D-dimensional linear cellular automata over \(Z_{m}\)
- Designing complex dynamics in cellular automata with memory
- Influence of the topology of a cellular automaton on its dynamical properties
- A complete and efficiently computable topological classification of D-dimensional linear cellular automata over Z m
- Complex dynamics of elementary cellular automata emerging from chaotic rules
- Classifying 1D elementary cellular automata with the 0-1 test for chaos
- Maximum sensitivity to update schedules of elementary cellular automata over periodic configurations
- On the reversibility of ECAs with fully asynchronous updating: the recurrence point of view
- Permutation binary neural networks: analysis of periodic orbits and its applications
- A tutorial on elementary cellular automata with fully asynchronous updating. General properties and convergence dynamics
- Computation and universality: Class IV versus Class III cellular automata
- Two elementary cellular automata with a new kind of dynamic
- Classification of cellular automata based on the Hamming distance
- Shift-equivalence of \(k\)-ary, one-dimensional cellular automata rules
- A comprehensive taxonomy of cellular automata
- Progress, gaps and obstacles in the classification of cellular automata
- Emergence of density dynamics by surface interpolation in elementary cellular automata
- An information-based classification of elementary cellular automata
- Chaos emerged on the `edge of chaos'
- A study of chaos in cellular automata
- Cellular automata complexity threshold and classification: a geometric perspective
- New aspects of symmetry of elementary cellular automata
- A study of chaos in non-uniform cellular automata
- scientific article; zbMATH DE number 2046048 (Why is no real title available?)
- A simple digital spiking neural network: synchronization and spike-train approximation
- Unraveling simplicity in elementary cellular automata
- Topological chaos of universal elementary cellular automata rule
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)
