On computing the Lyapunov exponents of reversible cellular automata



: Kopra Johan

: 2020

 Natural Computing

: NATURAL COMPUTING

: NAT COMPUT

: 14

: 1567-7818

: 1572-9796

DOI: https://doi.org/10.1007/s11047-020-09821-3

: https://link.springer.com/article/10.1007/s11047-020-09821-3

: https://research.utu.fi/converis/portal/detail/Publication/51281671


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.

Last updated on 26/11/2024 10:33:16 PM