A1 Refereed original research article in a scientific journal
On computing the Lyapunov exponents of reversible cellular automata
Authors: Kopra Johan
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
eISSN: 1572-9796
DOI: https://doi.org/10.1007/s11047-020-09821-3
Web address : https://link.springer.com/article/10.1007/s11047-020-09821-3
Self-archived copy’s web address: https://research.utu.fi/converis/portal/detail/Publication/51281671
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