A1 Journal article – refereed

On computing the Lyapunov exponents of reversible cellular automata

List of Authors: Johan Kopra

Publisher: Springer

Publication year: 2020

Journal: Natural Computing

Journal name in source: NATURAL COMPUTING

Journal acronym: NAT COMPUT

Number of pages: 14

ISSN: 1567-7818

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

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.

Downloadable publication

This is an electronic reprint of the original article.
This reprint may differ from the original in pagination and typographic detail. Please cite the original version.

Last updated on 2021-24-06 at 12:04