Rice’s Theorem for Generic Limit Sets of Cellular Automata - INSA CENTRE VAL DE LOIRE Accéder directement au contenu
Communication Dans Un Congrès Année : 2021

Rice’s Theorem for Generic Limit Sets of Cellular Automata

Résumé

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.
Fichier principal
Vignette du fichier
ricegeneric.pdf (708.28 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-04574261 , version 1 (14-05-2024)

Identifiants

Citer

Martin Delacourt. Rice’s Theorem for Generic Limit Sets of Cellular Automata. nternational Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA) 2021, Jul 2021, Marseille (CIRM, Centre International de Rencontres Mathématiques), France. pp.6:1 - 6:12, ⟨10.4230/OASIcs.AUTOMATA.2021.6⟩. ⟨hal-04574261⟩
0 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More