Skip to main contentSkip to search
Episciences
Open Access Journals
Sign in(new window)
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Sign in(new window)
Articles & Issues
All articlesAll accepted articlesAll volumesLast volumeSectionsSpecial issuesAuthors
About
The journalIndexing
Boards
Publish
For authorsEthical charter
Submit
Discrete Mathematics & Theoretical Computer Science logo
Contact
|
Credits
eISSN 1365-8050
|
RSS
|
Atom
Episciences
Documentation
|
Acknowledgements
|
Publishing policy
Accessibility: non-compliant
|
Legal mentions
|
Privacy statement
|
Terms of use
  1. Home > Articles & Issues >
  2. Articles >
  3. On undecidability of ...
Article

On undecidability of equicontinuity classification for cellular automata

Bruno Durand (1), Enrico Formenti ORCID (1), Georges Varouchas (1)
(1) Laboratoire d'informatique Fondamentale de Marseille - UMR 6166
Download article
Open on HAL
Imported on
November 21, 2016
Published on
December 31, 2002
Last modified on
March 31, 2025
Volume 0
DMTCS Proceedings vol. AB, Discrete Models for Complex Systems (DMCS'03)
Proceedings
DOI
10.46298/dmtcs.2302
License
https://about.hal.science/hal-authorisation-v1
Indicators
848
Views
570
Downloads

On undecidability of equicontinuity classification for cellular automata

Bruno Durand (1), Enrico Formenti ORCID (1), Georges Varouchas (1)
(1) Laboratoire d'informatique Fondamentale de Marseille - UMR 6166
Abstract
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.
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]
  • discrete dynamical systems
  • undecidability
  • cellular automata
  • classification
Mathematics Subject Classification 2020
  • 05C05 - Trees
  • 60C05 - Combinatorial probability
  • 60J10 - Markov chains (discrete-time Markov processes on discrete state spaces)
Cited by

Source: OpenCitations

  • Nonclassical Computation — A Dynamical Systems Perspective

    Handbook of Natural Computing

    Authors : Susan Stepney ORCID

    Journal reference : Volume , 2012, pp. 1979-2025

    DOI : 10.1007/978-3-540-92910-9_59
  • Basic Properties for Sand Automata

    Lecture notes in computer science

    Authors : J. Cervelle, E. Formenti ORCID, B. Masson

    Journal reference : Volume , 2005, pp. 192-211

    DOI : 10.1007/11549345_18
  • Towards a Rice Theorem on Traces of Cellular Automata

    Lecture notes in computer science

    Authors : Julien Cervelle, Pierre Guillon ORCID

    Journal reference : Volume , 2007, pp. 310-319

    DOI : 10.1007/978-3-540-74456-6_29
  • Nilpotency and periodic points in non-uniform cellular automata

    Acta Informatica

    Authors : Supreeti Kamilya ORCID, Jarkko Kari ORCID

    Journal reference : Volume 58, 2021, pp. 319-333

    DOI : 10.1007/s00236-020-00390-7
  • Computational Complexity of Rule Distributions of Non-uniform Cellular Automata

    Lecture notes in computer science

    Authors : Alberto Dennunzio ORCID, Enrico Formenti ORCID, Julien Provillard

    Journal reference : Volume , 2012, pp. 204-215

    DOI : 10.1007/978-3-642-28332-1_18
  • Some results about the chaotic behavior of cellular automata

    Theoretical Computer Science

    Authors : F. Blanchard ORCID, J. Cervelle, E. Formenti ORCID

    Journal reference : Volume 349, 2005, pp. 318-336

    DOI : 10.1016/j.tcs.2005.06.038
  • Descriptive Complexity of Sensitivity of Cellular Automata

    Authors : Tom Favereau, Ville Salo ORCID

    Journal reference : Volume , 2025, pp. 123-138

    DOI : 10.1007/978-3-032-01570-9_9
  • A full computation-relevant topological dynamics classification of elementary cellular automata

    Chaos An Interdisciplinary Journal of Nonlinear Science

    Authors : Martin Schüle, Ruedi Stoop

    Journal reference : Volume 22, 2012, pp. 043143

    DOI : 10.1063/1.4771662
  • Chaotic Behavior of Cellular Automata

    Encyclopedia of Complexity and Systems Science

    Authors : Julien Cervelle, Alberto Dennunzio ORCID, Enrico Formenti ORCID

    Journal reference : Volume , 2009, pp. 978-989

    DOI : 10.1007/978-0-387-30440-3_65
  • Self-referential basis of undecidable dynamics: From the Liar paradox and the halting problem to the edge of chaos

    arXiv (Cornell University)

    Authors : Mikhail Prokopenko ORCID, Michael Harré ORCID, Joseph Lizier ORCID, Fabio Boschetti ORCID, Pavlos Peppas ORCID, Stuart Kauffman ORCID

    Journal reference : Volume 31, 2019, pp. 134-156

    DOI : 10.1016/j.plrev.2018.12.003
  • Chaotic Behavior of Cellular Automata

    Computational Complexity

    Authors : Julien Cervelle, Alberto Dennunzio ORCID, Enrico Formenti ORCID

    Journal reference : Volume , 2011, pp. 479-489

    DOI : 10.1007/978-1-4614-1800-9_32
  • Theory of cellular automata: A survey

    Theoretical Computer Science

    Authors : Jarkko Kari ORCID

    Journal reference : Volume 334, 2005, pp. 3-33

    DOI : 10.1016/j.tcs.2004.11.021
  • Nondeterministic Cellular Automata

    Information Sciences

    Authors : Pietro Di Lena ORCID, Luciano Margara ORCID

    Journal reference : Volume 287, 2014, pp. 13-25

    DOI : 10.1016/j.ins.2014.07.007
  • On the conjugacy problem of cellular automata

    Information and Computation

    Authors : Joonatan Jalonen, Jarkko Kari ORCID

    Journal reference : Volume 274, 2020, pp. 104531

    DOI : 10.1016/j.ic.2020.104531
  • Particle filter data assimilation for ubiquitous unstable trajectories of two-dimensional three-state cellular automata

    Nonlinear Dynamics

    Authors : Ken Furukawa ORCID, Hideyuki Sakamoto, Marimo Ohhigashi, Shin-ichiro Shima ORCID, Travis Sluka ORCID, Takemasa Miyoshi ORCID

    Journal reference : Volume 112, 2024, pp. 21409-21424

    DOI : 10.1007/s11071-024-09803-5
  • Sofic Trace Subshift of a Cellular Automaton

    Lecture notes in computer science

    Authors : Julien Cervelle, Enrico Formenti ORCID, Pierre Guillon ORCID

    Journal reference : Volume , 2007, pp. 152-161

    DOI : 10.1007/978-3-540-73001-9_16
  • Basic Concepts of Cellular Automata

    Handbook of Natural Computing

    Authors : Jarkko J. Kari ORCID

    Journal reference : Volume , 2012, pp. 3-24

    DOI : 10.1007/978-3-540-92910-9_1
  • Decidability and undecidability in cellular automata

    International Journal of General Systems

    Authors : Jarkko Kari ORCID

    Journal reference : Volume 41, 2012, pp. 539-554

    DOI : 10.1080/03081079.2012.695895
  • On the directional dynamics of additive cellular automata

    Theoretical Computer Science

    Authors : A. Dennunzio ORCID, P. Di Lena ORCID, E. Formenti ORCID, L. Margara ORCID

    Journal reference : Volume 410, 2009, pp. 4823-4833

    DOI : 10.1016/j.tcs.2009.06.023
  • Topological Dynamics of Cellular Automata: Dimension Matters

    arXiv (Cornell University)

    Authors : Mathieu Sablik, Guillaume Theyssier

    Journal reference : Volume 48, 2010, pp. 693-714

    DOI : 10.1007/s00224-010-9255-x
  • Tiling Problem and Undecidability in Cellular Automata

    Encyclopedia of Complexity and Systems Science

    Authors : Jarkko Kari ORCID

    Journal reference : Volume , 2015, pp. 1-20

    DOI : 10.1007/978-3-642-27737-5_552-5
  • Decidable Properties for Regular Cellular Automata

    IFIP International Federation for Information Processing/IFIP

    Authors : Pietro Di Lena ORCID

    Journal reference : Volume , 2006, pp. 185-196

    DOI : 10.1007/978-0-387-34735-6_17
  • Toward Non Abelian Scenarios for Additive Cellular Automata on Finite Groups

    Lecture notes in computer science

    Authors : Alberto Dennunzio

    Journal reference : Volume , 2026, pp. 3-13

    DOI : 10.1007/978-3-032-15641-9_1
  • Tiling Problem and Undecidability in Cellular Automata

    Cellular Automata

    Authors : Jarkko Kari ORCID

    Journal reference : Volume , 2018, pp. 201-219

    DOI : 10.1007/978-1-4939-8700-9_552
  • Tiling Problem and Undecidability in Cellular Automata

    Encyclopedia of Complexity and Systems Science

    Authors : Jarkko Kari ORCID

    Journal reference : Volume , 2009, pp. 9158-9172

    DOI : 10.1007/978-0-387-30440-3_552
  • Theory of Cellular Automata: from the Past and Present to Some Path Towards the Future

    Lecture notes in computer science

    Authors : Alberto Dennunzio ORCID

    Journal reference : Volume , 2024, pp. 3-9

    DOI : 10.1007/978-3-031-71552-5_1
  • Topological Dynamics of 2D Cellular Automata

    Lecture notes in computer science

    Authors : Mathieu Sablik, Guillaume Theyssier

    Journal reference : Volume , 2008, pp. 523-532

    DOI : 10.1007/978-3-540-69407-6_56
  • Computational complexity of dynamical systems: The case of cellular automata

    Information and Computation

    Authors : P. Di Lena ORCID, L. Margara ORCID

    Journal reference : Volume 206, 2008, pp. 1104-1116

    DOI : 10.1016/j.ic.2008.03.012
  • Some Undecidable Dynamical Properties for One-Dimensional Reversible Cellular Automata

    Natural computing series

    Authors : Jarkko Kari ORCID, Ville Lukkarila

    Journal reference : Volume , 2009, pp. 639-660

    DOI : 10.1007/978-3-540-88869-7_32
  • Revisiting the Rice Theorem of Cellular Automata

    Authors : Guillon, Richard

    Journal reference : Volume , 2010, pp.

    DOI : 10.4230/lipics.stacs.2010.2474
  • Tiling Problem and Undecidability in Cellular Automata

    Computational Complexity

    Authors : Jarkko Kari ORCID

    Journal reference : Volume , 2011, pp. 3198-3211

    DOI : 10.1007/978-1-4614-1800-9_198
Preview
Loading PDF preview...