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