Computation and Universality: Class IV versus Class III Cellular Automata
arXiv:1304.1242
Abstract
This paper examines the claim that cellular automata (CA) belonging to Class III (in Wolfram's classification) are capable of (Turing universal) computation. We explore some chaotic CA (believed to belong to Class III) reported over the course of the CA history, that may be candidates for universal computation, hence spurring the discussion on Turing universality on both Wolfram's classes III and IV.
arXiv admin note: substantial text overlap with arXiv:1208.2456
References in corpus (9)
- Revisiting the Edge of Chaos: Evolving Cellular Automata to Perform Computations
- A Concrete View of Rule 110 Computation
- Determining a regular language by glider-based structures called phases fi_1 in Rule 110
- Searching for Spaceships
- Expressiveness of Elementary Cellular Automata
- Crystalline Computation
- Localization dynamics in a binary two-dimensional cellular automaton: the Diffusion Rule
- Complex dynamics emerging in Rule 30 with majority memory
- On logical gates in precipitating medium: cellular automaton model
Cited by in corpus (8)
- Integrated information as a common signature of dynamical and information-processing complexity
- Deep Learning as a Parton Shower
- Self-referential basis of undecidable dynamics: from The Liar Paradox and The Halting Problem to The Edge of Chaos
- Designing Complex Dynamics in Cellular Automata with Memory
- A Behavioural Foundation for Natural Computing and a Programmability Test
- What is Nature-like Computation? A Behavioural Approach and a Notion of Programmability
- Simple networks on complex cellular automata: From de Bruijn diagrams to jump-graphs
- Stability of cellular automata trajectories revisited: branching walks and Lyapunov profiles