A4 Vertaisarvioitu artikkeli konferenssijulkaisussa
The Lyapunov Exponents of Reversible Cellular Automata Are Uncomputable
Tekijät: Kopra J.
Toimittaja: Ian McQuillan, Shinnosuke Seki
Konferenssin vakiintunut nimi: International Conference on Unconventional Computation and Natural Computation
Kustantaja: Springer Verlag
Julkaisuvuosi: 2019
Journal: Lecture Notes in Computer Science
Kokoomateoksen nimi: Unconventional Computation and Natural Computation : 18th International Conference, UCNC 2019, Tokyo, Japan, June 3–7, 2019, Proceedings
Tietokannassa oleva lehden nimi: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Sarjan nimi: Lecture Notes in Computer Science
Vuosikerta: 11493
ISBN: 978-3-030-19310-2
eISBN: 978-3-030-19311-9
ISSN: 0302-9743
DOI: https://doi.org/10.1007/978-3-030-19311-9_15
Rinnakkaistallenteen osoite: https://research.utu.fi/converis/portal/detail/Publication/41254647
We will show that the class of reversible cellular automata (CA) with right Lyapunov exponent 2 cannot be separated algorithmically from the class of reversible CA whose right Lyapunov exponents are at most 2−δ for some absolute constant δ>0. Therefore there is no algorithm that, given as an input a description of an arbitrary reversible CA F and a positive rational number ϵ>0, outputs the Lyapunov exponents of F with accuracy ϵ.
Ladattava julkaisu This is an electronic reprint of the original article. |  |
