Classifying circular cellular automata

DOI10.1016/0167-2789(90)90196-VzbMath0729.68065OpenAlexW2032405796MaRDI QIDQ807056

Klaus Sutner

Publication date: 1990

Published in: Physica D (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0167-2789(90)90196-v

zbMATH Keywords

undecidabilitycellular automataperiodic configurationssimulation of Turing machines on circular cellular automata

Mathematics Subject Classification ID

Cellular automata (computational aspects) (68Q80)

Related Items (15)

The complexity of reversible cellular automata ⋮ An analysis of different types and effects of asynchronicity in cellular automata update schemes ⋮ The ``magic rule spaces of neural-like elementary cellular automata ⋮ Computational processes, observers and Turing incompleteness ⋮ Cellular automata and intermediate degrees. ⋮ A class of discrete dynamical systems with properties of both cellular automata and L-systems ⋮ Cellular automata in fuzzy backgrounds ⋮ \(\sigma\)-Automata and Chebyshev-polynomials ⋮ Pattern growth in elementary cellular automata ⋮ ITERATION OF INVERTIBLE TRANSDUCTIONS ⋮ What Do We Mean by Asynchronous CA? A Reflection on Types and Effects of Asynchronicity ⋮ On the Asymptotic Behavior of Fuzzy Cellular Automata ⋮ Additive one-dimensional cellular automata are chaotic according to Devaney's definition of chaos ⋮ Investigating topological chaos by elementary cellular automata dynamics ⋮ Global fixed point attractors of circular cellular automata and periodic tilings of the plane: Undecidability results

Cites Work

• The constructibility of a configuration in a cellular automaton
• Reversibility of 2D cellular automata is undecidable
• Algebraic properties of cellular automata
• Computation theory of cellular automata
• On the computational complexity of finite cellular automata
• Decision procedures for surjectivity and injectivity of parallel maps for tessellation structures
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Classifying circular cellular automata