Rice's theorem for generic limit sets of cellular automata

The generic limit set of a cellular automaton is a topologically dened set of congurations that intends to capture the asymptotic behaviours while avoiding atypical ones. It was dened by Milnor then studied by Djenaoui and Guillon rst, and by T{\"o}rm{\"a} later. They gave properties of th...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2021-06
Main Author: Delacourt, Martin
Format: Article
Language:English
Subjects:
Asymptotic properties
Cellular automata
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The generic limit set of a cellular automaton is a topologically dened set of congurations that intends to capture the asymptotic behaviours while avoiding atypical ones. It was dened by Milnor then studied by Djenaoui and Guillon rst, and by T{\"o}rm{\"a} 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.
ISSN:2331-8422