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 CA that perform multiplication by $p$ in base $pq$ for coprime $p,q>1$.

arXiv comment19 pages, 6 figures, submitted to Natural Computing