Dynamics of Automata under different update schedules.

Abstract

In this thesis our main interest is focused specically on the dynamics of cellular automata. Dynamics will be addressed by the invariance of the automaton, and in some cases invariance will be addressed by its reversibility. Our concept of invariance will be considered under the set of attractors of the automaton, i.e. it's periodic congurations. This concept suggests to question the robustness of the automaton, this is, the stability of the behaviour regardless external dis- turbances, such as dierent update schedules. This is important in dynamical systems, in order to determine and prove strong properties that are invariant under structural modifications. More precisely, we have studied the block invariance and attractor invari- ance of the elementary cellular automata, Section 3.1 and 3.2 respectively, and invariance of linear rules with radius 2, Section 4.2. On the one hand, we have studied 11 conjectures about block invariance, that were previously established in [7]. We were able to prove 9 of them and refute the other 2 left. Also, for all 256 elementary cellular automata we established equivalences in between them by means of the congurations of their set of attractors. In the case of attractor invariance we managed to characterize the set of attractor of the elementary cellular automata rules under sequential update schedules, so to establish equiv-alences (classes) in between these rules by means of the congurations of their set of attractors. We have proven 2 of these classes, leaving the rest of them as future work. On the other hand, we were able to characterize the update schedules for which the linear rules 90 and 150 are invariant, and the same was done for linear rules with radius 2. The key tool to prove invariance for linear rules was the study of the reversibility of each rule. Due to this work we have published two articles, [8, 11].