License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/OASIcs.AUTOMATA.2021.6
URN: urn:nbn:de:0030-drops-140151
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14015/
Delacourt, Martin
Rice’s Theorem for Generic Limit Sets of Cellular Automata
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.
BibTeX - Entry
@InProceedings{delacourt:OASIcs.AUTOMATA.2021.6,
author = {Delacourt, Martin},
title = {{Rice’s Theorem for Generic Limit Sets of Cellular Automata}},
booktitle = {27th IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA 2021)},
pages = {6:1--6:12},
series = {Open Access Series in Informatics (OASIcs)},
ISBN = {978-3-95977-189-4},
ISSN = {2190-6807},
year = {2021},
volume = {90},
editor = {Castillo-Ramirez, Alonso and Guillon, Pierre and Perrot, K\'{e}vin},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14015},
URN = {urn:nbn:de:0030-drops-140151},
doi = {10.4230/OASIcs.AUTOMATA.2021.6},
annote = {Keywords: cellular automata, dynamical systems, generic-limit sets, Rice’s theorem, subshifts}
}
|
Keywords: |
|
cellular automata, dynamical systems, generic-limit sets, Rice’s theorem, subshifts |
|
Collection: |
|
27th IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA 2021) |
|
Issue Date: |
|
2021 |
|
Date of publication: |
|
28.06.2021 |
