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 1; Enrico Formenti 1; Georges Varouchas 1
NULL##0000-0002-1007-7912##NULL
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.
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.
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.
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.
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.