A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
On computing the Lyapunov exponents of reversible cellular automata
Tekijät: Kopra Johan
Kustantaja: Springer
Julkaisuvuosi: 2020
Journal: Natural Computing
Tietokannassa oleva lehden nimi: NATURAL COMPUTING
Lehden akronyymi: NAT COMPUT
Sivujen määrä: 14
ISSN: 1567-7818
eISSN: 1572-9796
DOI: https://doi.org/10.1007/s11047-020-09821-3
Verkko-osoite: https://link.springer.com/article/10.1007/s11047-020-09821-3
Rinnakkaistallenteen osoite: https://research.utu.fi/converis/portal/detail/Publication/51281671
Tiivistelmä
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.
Ladattava julkaisu This is an electronic reprint of the original article. |  |
Turun yliopiston Tutkimustietojärjestelmän portaali