Search

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]

Abstract: This paper studies directional dynamics on one-dimensional cellular automata, a formalism previously introduced by the third author. The central idea is to study the dynamical behavior of a cellular automaton through the conjoint action of its global rule (temporal action) and the shift map (spacial action): qualitative behaviors inherited from topological dynamics (equicontinuity, sensitivity, expansivity) are thus considered along arbitrary curves in space–time. The main contributions of the paper concern equicontinuous dynamics which can be connected to the notion of consequences of a word. We show that there is a cellular automaton with an equicontinuous dynamics along a parabola, but which is sensitive along any linear direction. We also show that real numbers that occur as the slope of a limit linear direction with equicontinuous dynamics in some cellular automaton are exactly the computably enumerable numbers. [Copyright &y& Elsevier]