On undecidability of equicontinuity classification for cellular automata

Bruno Durand; Enrico Formenti; Georges Varouchas

doi:10.46298/dmtcs.2302

Bruno Durand ; Enrico Formenti ; Georges Varouchas - On undecidability of equicontinuity classification for cellular automata

dmtcs:2302 - Discrete Mathematics & Theoretical Computer Science, January 1, 2003, DMTCS Proceedings vol. AB, Discrete Models for Complex Systems (DMCS'03) - https://doi.org/10.46298/dmtcs.2302

On undecidability of equicontinuity classification for cellular automataArticle

Authors: Bruno Durand ¹; Enrico Formenti ¹; Georges Varouchas ¹

1 Laboratoire d'informatique Fondamentale de Marseille - UMR 6166

Equicontinuity classification is a popular classification of cellular automata based on their dynamical behavior. In this paper we prove that most of its classes are undecidable.

https://doi.org/10.46298/dmtcs.2302

Source: HAL:hal-01183309v1

Volume: DMTCS Proceedings vol. AB, Discrete Models for Complex Systems (DMCS'03)

Section: Proceedings

Published on: January 1, 2003

Imported on: November 21, 2016

Keywords: discrete dynamical systems,undecidability,cellular automata,classification,[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM],[MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO],[NLIN.NLIN-CG]Nonlinear Sciences [physics]/Cellular Automata and Lattice Gases [nlin.CG],[INFO.INFO-HC]Computer Science [cs]/Human-Computer Interaction [cs.HC]

Classifications

Mathematics Subject Classification 2020¹

Sources:

[1] zbMATH Open.

Bibliographic References

28 Documents citing this article

Alberto Dennunzio, Lecture notes in computer science, Theory of Cellular Automata: from the Past and Present to Some Path Towards the Future, pp. 3-9, 2024, 10.1007/978-3-031-71552-5_1.

Ken Furukawa;Hideyuki Sakamoto;Marimo Ohhigashi;Shin-ichiro Shima;Travis Sluka;et al., 2024, Particle filter data assimilation for ubiquitous unstable trajectories of two-dimensional three-state cellular automata, Nonlinear Dynamics, 112, 23, pp. 21409-21424, 10.1007/s11071-024-09803-5, https://doi.org/10.1007/s11071-024-09803-5.

Supreeti Kamilya;Jarkko Kari, 2021, Nilpotency and periodic points in non-uniform cellular automata, Acta Informatica, 58, 4, pp. 319-333, 10.1007/s00236-020-00390-7, https://doi.org/10.1007/s00236-020-00390-7.

Joonatan Jalonen;Jarkko Kari, 2020, On the conjugacy problem of cellular automata, Information and Computation, 274, pp. 104531, 10.1016/j.ic.2020.104531, https://doi.org/10.1016/j.ic.2020.104531.

Mikhail Prokopenko;Michael Harré;Joseph Lizier;Fabio Boschetti;Pavlos Peppas;et al., 2019, Self-referential basis of undecidable dynamics: From the Liar paradox and the halting problem to the edge of chaos, arXiv (Cornell University), 31, pp. 134-156, 10.1016/j.plrev.2018.12.003, https://arxiv.org/abs/1711.02456.

Jarkko Kari, Springer eBooks, Tiling Problem and Undecidability in Cellular Automata, pp. 201-219, 2018, 10.1007/978-1-4939-8700-9_552.

Jarkko Kari, Encyclopedia of Complexity and Systems Science, Tiling Problem and Undecidability in Cellular Automata, pp. 1-20, 2015, 10.1007/978-3-642-27737-5_552-5.

Pietro Di Lena;Luciano Margara, 2014, Nondeterministic Cellular Automata, Information Sciences, 287, pp. 13-25, 10.1016/j.ins.2014.07.007.

Alberto Dennunzio;Enrico Formenti;Julien Provillard, Computational Complexity of Rule Distributions of Non-uniform Cellular Automata, pp. 204-215, 2012, 10.1007/978-3-642-28332-1_18, https://hal.archives-ouvertes.fr/hal-01297574.

Jarkko J. Kari, Springer eBooks, Basic Concepts of Cellular Automata, pp. 3-24, 2012, 10.1007/978-3-540-92910-9_1.

Martin Schüle;Ruedi Stoop, 2012, A full computation-relevant topological dynamics classification of elementary cellular automata, arXiv (Cornell University), 22, 4, 10.1063/1.4771662, http://arxiv.org/abs/1107.2080.

Susan Stepney, Springer eBooks, Nonclassical Computation — A Dynamical Systems Perspective, pp. 1979-2025, 2012, 10.1007/978-3-540-92910-9_59.

Jarkko Kari, Computational Complexity, Tiling Problem and Undecidability in Cellular Automata, pp. 3198-3211, 2011, 10.1007/978-1-4614-1800-9_198.

Julien Cervelle;Alberto Dennunzio;Enrico Formenti, Computational Complexity, Chaotic Behavior of Cellular Automata, pp. 479-489, 2011, 10.1007/978-1-4614-1800-9_32.

Mathieu Sablik;Guillaume Theyssier, 2010, Topological Dynamics of Cellular Automata: Dimension Matters, 48, 3, pp. 693-714, 10.1007/s00224-010-9255-x, https://hal.archives-ouvertes.fr/hal-00339354.

Pierre Guillon;Gaétan Richard, Revisiting the Rice Theorem of Cellular Automata, 5, pp. 441-452, 2010, 10.4230/lipics.stacs.2010.2474.

A. Dennunzio;P. Di Lena;E. Formenti;L. Margara, 2009, On the directional dynamics of additive cellular automata, Theoretical Computer Science, 410, 47-49, pp. 4823-4833, 10.1016/j.tcs.2009.06.023, https://doi.org/10.1016/j.tcs.2009.06.023.

Jarkko Kari, Encyclopedia of Complexity and Systems Science, Tiling Problem and Undecidability in Cellular Automata, pp. 9158-9172, 2009, 10.1007/978-0-387-30440-3_552.

Jarkko Kari;Ville Lukkarila, Natural computing series, Some Undecidable Dynamical Properties for One-Dimensional Reversible Cellular Automata, pp. 639-660, 2009, 10.1007/978-3-540-88869-7_32.

Julien Cervelle;Alberto Dennunzio;Enrico Formenti, Encyclopedia of Complexity and Systems Science, Chaotic Behavior of Cellular Automata, pp. 978-989, 2009, 10.1007/978-0-387-30440-3_65.

Mathieu Sablik;Guillaume Theyssier, Topological Dynamics of 2D Cellular Automata, pp. 523-532, 2008, 10.1007/978-3-540-69407-6_56, https://hal.science/hal-00175396v3/file/HALpaper.pdf.

P. Di Lena;L. Margara, 2008, Computational complexity of dynamical systems: The case of cellular automata, CiteSeer X (The Pennsylvania State University), 206, 9-10, pp. 1104-1116, 10.1016/j.ic.2008.03.012, http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.496.943.

Julien Cervelle;Enrico Formenti;Pierre Guillon, Lecture notes in computer science, Sofic Trace Subshift of a Cellular Automaton, pp. 152-161, 2007, 10.1007/978-3-540-73001-9_16.

Julien Cervelle;Pierre Guillon, Towards a Rice Theorem on Traces of Cellular Automata, pp. 310-319, 2007, 10.1007/978-3-540-74456-6_29, https://hal.science/hal-00620284.

Pietro Di Lena, IFIP International Federation for Information Processing/IFIP, Decidable Properties for Regular Cellular Automata, pp. 185-196, 2006, 10.1007/978-0-387-34735-6_17, https://doi.org/10.1007/978-0-387-34735-6_17.

F. Blanchard;J. Cervelle;E. Formenti, 2005, Some results about the chaotic behavior of cellular automata, Theoretical Computer Science, 349, 3, pp. 318-336, 10.1016/j.tcs.2005.06.038.

J. Cervelle;E. Formenti;B. Masson, Basic Properties for Sand Automata, pp. 192-211, 2005, 10.1007/11549345_18, https://hal.archives-ouvertes.fr/hal-00003208.

Jarkko Kari, 2005, Theory of cellular automata: A survey, Theoretical Computer Science, 334, 1-3, pp. 3-33, 10.1016/j.tcs.2004.11.021.

Sources : OpenCitations, OpenAlex & Crossref

Share and export

Consultation statistics

This page has been seen 408 times.

This article's PDF has been downloaded 320 times.