mu-Limit sets of cellular automata from a computational complexity perspective

作者：Boyer L; Delacourt M^*; Poupet V; Sablik M; Theyssier G

来源：Journal of Computer and System Sciences, 2015, 81(8): 1623-1647.

DOI：10.1016/j.jcss.2015.05.004

• Cellular automata
• mu-Limit sets
• Rice theorem
• Arithmetical hierarchy

This paper concerns mu-limit sets of cellular automata: sets of configurations made of words whose probability to appear does not vanish with time, starting from an initial mu-random configuration. More precisely, we investigate the computational complexity of these sets and of related decision problems. Main results: first, mu-limit sets can have a Sigma(0)(3)-hard language, second, they can contain only a-complex configurations, third, any nontrivial property concerning them is at least Pi(0)(3)-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.

• 出版日期2015-12