2020/01/27 by Johan Kopra, Kopra, Johan
Mathematics · Physics and Astronomy · #37B15 #Cellular Automata and Lattice Gases (nlin.CG) #Dynamical Systems (math.DS) #FOS: Mathematics #FOS: Physical sciences #math.DS #msc:37B15 #nlin.CG
paper · pdf · doi:10.48550/arxiv.2001.09675
19 pages, 6 figures, submitted to Natural Computing
arxiv created 2020/01/27 · arxiv updated 2020/01/28
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-δ for some absolute constant δ>0. Therefore there is no algorithm that, given as an input a description of an arbitrary reversible CA F and a positive rational number ε>0, outputs the Lyapunov exponents of F with accuracy ε. 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.