OASIcs.AUTOMATA.2021.6.pdf
- Filesize: 0.95 MB
- 12 pages
Document
Rice’s Theorem for Generic Limit Sets of Cellular Automata
Author
-
Part of:
Volume:
27th IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA 2021)
Series: Open Access Series in Informatics (OASIcs)
Conference: International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2021-06-28
Cite As Get BibTex
Martin Delacourt. Rice’s Theorem for Generic Limit Sets of Cellular Automata. In 27th IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA 2021). Open Access Series in Informatics (OASIcs), Volume 90, pp. 6:1-6:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/OASIcs.AUTOMATA.2021.6
Abstract
The generic limit set of a cellular automaton is a topologically defined set of configurations that intends to capture the asymptotic behaviours while avoiding atypical ones. It was defined by Milnor then studied by Djenaoui and Guillon first, and by Törmä later. They gave properties of this set related to the dynamics of the cellular automaton, and the maximal complexity of its language. In this paper, we prove that every non trivial property of these generic limit sets of cellular automata is undecidable.
Subject Classification
ACM Subject Classification
- Theory of computation → Models of computation
Keywords
- cellular automata
- dynamical systems
- generic-limit sets
- Rice’s theorem
- subshifts
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Laurent Boyer, Martin Delacourt, Victor Poupet, Mathieu Sablik, and Guillaume Theyssier. μ-limit sets of cellular automata from a computational complexity perspective. Journal of Computer and System Sciences, 81, September 2013. URL: https://doi.org/10.1016/j.jcss.2015.05.004.
- Benjamin Hellouin de Menibus and Mathieu Sablik. Characterisation of sets of limit measures after iteration of a cellular automaton on an initial measure. CoRR, abs/1301.1998, 2013. URL: http://arxiv.org/abs/1301.1998.
- Martin Delacourt. Rice’s theorem for μ-limit sets of cellular automata. In ICALP (2), pages 89-100, 2011. URL: https://doi.org/10.1007/978-3-642-22012-8_6.
- Saliha Djenaoui and Pierre Guillon. The generic limit set of cellular automata. working paper or preprint, 2018. URL: https://hal.archives-ouvertes.fr/hal-01861590.
- Gustav Arnold Hedlund. Endomorphisms and automorphisms of the shift dynamical systems. Mathematical Systems Theory, 3(4):320-375, 1969. URL: https://doi.org/10.1007/BF01691062.
-
Karel Culik II, Jan Pachl, and Sheng Yu. On the limit sets of cellular automata. SIAM Journal on Computing, 18(4):831-842, 1989.
- Jarkko Kari. The nilpotency problem of one-dimensional cellular automata. SIAM Journal on Computing, 21:571-586, 1992. URL: https://doi.org/10.1137/0221036.
- Jarkko Kari. Rice’s theorem for the limit sets of cellular automata. Theoretical Computer Science, 127:229-254, 1994. URL: https://doi.org/10.1016/0304-3975(94)90041-8.
- Jarkko Kari. Theory of cellular automata: A survey. Theoretical Computer Science, 334(1):3-33, 2005. URL: https://doi.org/10.1016/j.tcs.2004.11.021.
-
Petr Kůrka and Alejandro Maass. Limit sets of cellular automata associated to probability measures. Journal of Statistical Physics, 100(5-6):1031-1047, 2000.
- John Milnor. On the concept of attractor. Communications in Mathematical Physics, 99(2):177-195, 1985. URL: https://doi.org/10.1007/BF01212280.
-
Ilkka Törmä. Complexity of generic limit sets of cellular automata. In Hector Zenil, editor, Cellular Automata and Discrete Complex Systems, pages 126-138, Cham, 2020. Springer International Publishing.
-
John von Neumann. Theory of Self-Reproducing Automata. University of Illinois Press, Champaign, IL, USA, 1966.