We define the class of rapidly left expansive cellular automata, which contains Wolfram's Rule 30, fractional multiplication automata, and many others. Previous results on aperiodicity of columns in space-time diagrams of certain cellular automata generalize to this new class. We also present conditions that imply periodic behavior in cellular automata and use these to prove new results on rapidly left expansive cellular automata that originate from the theory of distribution modulo 1.

Abstract We consider the problem of computing the Lyapunov exponents of reversible cellular automata (CA). We show that the class of reversible CA with right Lyapunov exponent 2 cannot be separated algorithmically from the class of reversible CA whose right Lyapunov exponents are at most $$2-\delta$$ 2 - δ for some absolute constant $$\delta >0$$ δ > 0 . Therefore there is no algorithm that, given as an input a description of an arbitrary reversible CA F and a positive rational number $$\epsilon >0$$ ϵ > 0 , outputs the Lyapunov exponents of F with accuracy $$\epsilon$$ ϵ . We also compute the average Lyapunov exponents (with respect to the uniform measure) of the reversible CA that perform multiplication by p in base pq for coprime $$p,q>1$$ p , q > 1 .

Abstract For any mixing SFT X we construct a reversible shift-commuting continuous map (automorphism) which breaks any given finite point of the subshift into a finite collection of gliders traveling into opposing directions. As an application we prove a finitary Ryan’s theorem: the automorphism group $${{\,\mathrm{Aut}\,}}(X)$$ Aut ( X ) contains a two-element subset S whose centralizer consists only of shift maps. We also give an example which shows that a stronger finitary variant of Ryan’s theorem does not hold even for the binary full shift.