On computing the Lyapunov exponents of reversible cellular automata

DOI10.1007/978-3-030-19311-9_15arXiv2001.09675MaRDI QIDQ6333540

Johan Kopra

Publication date: 27 January 2020

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$.

Mathematics Subject Classification ID

Cellular automata (computational aspects) (68Q80) Dynamical aspects of cellular automata (37B15)

This page was built for publication: On computing the Lyapunov exponents of reversible cellular automata

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6333540)