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 automata
Authors: Bruno Durand ; Enrico Formenti ; Georges Varouchas
NULL##NULL##NULL
Bruno Durand;Enrico Formenti;Georges Varouchas
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.
Di Lena, Pietro; Margara, Luciano, 2014, Nondeterministic Cellular Automata, Information Sciences, 287, pp. 13-25, 10.1016/j.ins.2014.07.007.
Kari, Jarkko, 2012, Tiling Problem And Undecidability In Cellular Automata, Computational Complexity, pp. 3198-3211, 10.1007/978-1-4614-1800-9_198.
Kari, Jarkko, 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.
Kari, Jarkko J., 2012, Basic Concepts Of Cellular Automata, Handbook Of Natural Computing, pp. 3-24, 10.1007/978-3-540-92910-9_1.
Sablik, Mathieu; Theyssier, Guillaume, 2008, Topological Dynamics Of 2D Cellular Automata, Logic And Theory Of Algorithms - Lecture Notes In Computer Science, pp. 523-532, 10.1007/978-3-540-69407-6_56, http://arxiv.org/pdf/0709.4565.