On the undecidability of the limit behavior of cellular automata

DOI10.1016/J.TCS.2009.11.016MaRDI QIDQ2268864zbMATH OpenOpenAlexFDO

Authors 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

cellular automatasymbolic dynamicsundecidability

Mathematics Subject Classification ID

Cellular automata (computational aspects) (68Q80)

Recommendations

• Undecidable properties of limit set dynamics of cellular automata
• scientific article; zbMATH DE number 919608
• Revisiting the Rice theorem of cellular automata
• On the Limit Sets of Cellular Automata
• On the undecidability of attractor properties for cellular automata

Cites work

• An Introduction to Symbolic Dynamics and Coding
• Attractors in cellular automata
• Conservation of some dynamical properties for operations on cellular automata
• Decidable Properties of 2D Cellular Automata
• Directional dynamics for cellular automata: A sensitivity to initial condition approach
• scientific article; zbMATH DE number 4191143 (Why is no real title available?)
• scientific article; zbMATH DE number 4195191 (Why is no real title available?)
• scientific article; zbMATH DE number 2046045 (Why is no real title available?)
• Languages, equicontinuity and attractors in cellular automata
• On the directional dynamics of additive cellular automata
• On the sofic limit sets of cellular automata
• Rice's theorem for the limit sets of cellular automata
• Shifting and Lifting of Cellular Automata
• Subshift attractors of cellular automata
• The Nilpotency Problem of One-Dimensional Cellular Automata

Cited in

(17)

• Topological dynamics of nondeterministic cellular automata
• On the undecidability of attractor properties for cellular automata
• On stable and unstable limit sets of finite families of cellular automata
• On the Limit Sets of Cellular Automata
• Revisiting the Rice theorem of cellular automata
• Multidimensional cellular automata: closing property, quasi-expansivity, and (un)decidability issues
• Local rule distributions, language complexity and non-uniform cellular automata
• Inferring the Limit Behavior of Some Elementary Cellular Automata
• scientific article; zbMATH DE number 919608 (Why is no real title available?)
• Some Formal Properties of Asynchronous Cellular Automata
• Nondeterministic cellular automata
• Turing degrees of limit sets of cellular automata
• scientific article; zbMATH DE number 270137 (Why is no real title available?)
• Undecidable properties of limit set dynamics of cellular automata
• Extensions on the analysis of elementary cellular automata with process graphs
• Nash equilibria and undecidability in generic physical interactions -- a free energy perspective
• Non-uniform cellular automata: classes, dynamics, and decidability

This page was built for publication: On the undecidability of the limit behavior of cellular automata

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2268864)