Rice’s Theorem for Generic Limit Sets of Cellular Automata

Delacourt, Martin

doi:10.4230/OASIcs.AUTOMATA.2021.6

File

OASIcs.AUTOMATA.2021.6.pdf

Filesize: 0.95 MB
12 pages

Document Identifiers

DOI: 10.4230/OASIcs.AUTOMATA.2021.6
URN: urn:nbn:de:0030-drops-140151

Author Details

Martin Delacourt

Université d'Orléans, LIFO EA4022, FR-45067 Orléans, France

Cite AsGet 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)

0

PDF Downloads

0

Metadata Views

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.