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: [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], [en] discrete dynamical systems, undecidability, cellular automata, classification

Classifications

Mathematics Subject Classification 2020¹

Sources:

[1] zbMATH Open.

Bibliographic References

28 Documents citing this article

Alberto Dennunzio, 2024, Theory of Cellular Automata: from the Past and Present to Some Path Towards the Future, Lecture notes in computer science, pp. 3-9, 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.

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, http://arxiv.org/abs/1711.02456.

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

Jarkko Kari, 2015, Tiling Problem and Undecidability in Cellular Automata, Encyclopedia of Complexity and Systems Science, pp. 1-20, 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, 2012, Computational Complexity of Rule Distributions of Non-uniform Cellular Automata, pp. 204-215, 10.1007/978-3-642-28332-1_18, https://hal.science/hal-01297574.

Jarkko J. Kari, 2012, Basic Concepts of Cellular Automata, Handbook of Natural Computing, pp. 3-24, 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, Chaos An Interdisciplinary Journal of Nonlinear Science, 22, 4, pp. 043143, 10.1063/1.4771662, https://doi.org/10.1063/1.4771662.

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

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

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

Mathieu Sablik;Guillaume Theyssier, 2010, Topological Dynamics of Cellular Automata: Dimension Matters, arXiv (Cornell University), 48, 3, pp. 693-714, 10.1007/s00224-010-9255-x, http://arxiv.org/abs/0811.2731.

Pierre Guillon;Gaétan Richard, 2010, Revisiting the Rice Theorem of Cellular Automata, Dagstuhl Research Online Publication Server, 10.4230/lipics.stacs.2010.2474, https://doi.org/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.

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

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

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

Mathieu Sablik;Guillaume Theyssier, 2008, Topological Dynamics of 2D Cellular Automata, Lecture notes in computer science, pp. 523-532, 10.1007/978-3-540-69407-6_56.

P. Di Lena;L. Margara, 2008, Computational complexity of dynamical systems: The case of cellular automata, Information and Computation, 206, 9-10, pp. 1104-1116, 10.1016/j.ic.2008.03.012.

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

Julien Cervelle;Pierre Guillon, 2007, Towards a Rice Theorem on Traces of Cellular Automata, Lecture notes in computer science, pp. 310-319, 10.1007/978-3-540-74456-6_29.

Pietro Di Lena, 2006, Decidable Properties for Regular Cellular Automata, IFIP International Federation for Information Processing/IFIP, pp. 185-196, 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, 2005, Basic Properties for Sand Automata, Lecture notes in computer science, pp. 192-211, 10.1007/11549345_18.

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 548 times.

This article's PDF has been downloaded 374 times.