On the undecidability of the limit behavior of cellular automata

DOI10.1016/j.tcs.2009.11.016zbMath1186.68309OpenAlexW1996207390MaRDI QIDQ2268864

Pietro Di Lena, Luciano Margara

Publication date: 9 March 2010

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2009.11.016

zbMATH Keywords

undecidabilitycellular automatasymbolic dynamics

Mathematics Subject Classification ID

Cellular automata (computational aspects) (68Q80)

Related Items

Local rule distributions, language complexity and non-uniform cellular automata ⋮ Topological dynamics of nondeterministic cellular automata ⋮ Nondeterministic cellular automata ⋮ Some Formal Properties of Asynchronous Cellular Automata ⋮ Non-uniform cellular automata: classes, dynamics, and decidability

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Conservation of some dynamical properties for operations on cellular automata
• Directional dynamics for cellular automata: A sensitivity to initial condition approach
• On the directional dynamics of additive cellular automata
• Rice's theorem for the limit sets of cellular automata
• Decidable Properties of 2D Cellular Automata
• Attractors in cellular automata
• The Nilpotency Problem of One-Dimensional Cellular Automata
• Languages, equicontinuity and attractors in cellular automata
• On the sofic limit sets of cellular automata
• An Introduction to Symbolic Dynamics and Coding
• Subshift attractors of cellular automata
• Shifting and Lifting of Cellular Automata