\(\mu\)-limit sets of cellular automata from a computational complexity perspective (Q494067)

The limit set of a cellular automaton is the set of configurations that can appear arbitrarily far in time. Any nontrivial property of limit sets is undecidable. More refined notions have been studied, e.g. considering the notion of attractor. The framework of the paper assumes that the initial configuration is chosen randomly according to a measure \(\mu\). The set of interest contains the configurations which are observed when a random configuration is iterated. The authors model this set using the mathematical notion of \(\mu\)-limit set, which is a subshift whose forbidden patterns are exactly those whose probabilities tend to zero as time tends to infinity. The paper then investigate the computational complexity of \(\mu\)-limit sets and related decision problems. The main results are: a) \(\mu\)-limit sets can have a \(\Sigma_{3}^{0}\)-hard language, can contain only \(\alpha\)-complex configurations; b) any non-trivial property of \(\mu\)-limit sets is at least \(\Sigma_{3}^{0}\)-hard.