1. μ-Limit sets of cellular automata from a computational complexity perspective.
- Author
-
Boyer, L., Delacourt, M., Poupet, V., Sablik, M., and Theyssier, G.
- Subjects
- *
SET theory , *CELLULAR automata , *COMPUTATIONAL complexity , *PROBABILITY theory , *STATISTICAL decision making , *MATHEMATICAL bounds - Abstract
This paper concerns μ -limit sets of cellular automata: sets of configurations made of words whose probability to appear does not vanish with time, starting from an initial μ -random configuration. More precisely, we investigate the computational complexity of these sets and of related decision problems. Main results: first, μ -limit sets can have a Σ 3 0 -hard language, second, they can contain only α -complex configurations, third, any non-trivial property concerning them is at least Π 3 0 -hard. We prove complexity upper bounds, study restrictions of these questions to particular classes of CA, and different types of (non-)convergence of the measure of a word during the evolution. [ABSTRACT FROM AUTHOR]
- Published
- 2015
- Full Text
- View/download PDF