On computing the Lyapunov exponents of reversible cellular automata

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 for some absolute constant delta>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, 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.