2026-07-24T02:47:01Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14015 2024-03-06T10:31:18Z ddc:004 open_access

Rice’s Theorem for Generic Limit Sets of Cellular Automata Delacourt, Martin cellular automata dynamical systems generic-limit sets Rice’s theorem subshifts 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Martin Delacourt 2021 Is Part Of OASIcs, Volume 90, 27th IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/OASIcs.AUTOMATA.2021.6 urn:nbn:de:0030-drops-140151 https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.AUTOMATA.2021.6 eng https://creativecommons.org/licenses/by/4.0/legalcode