A4 Refereed article in a conference publication

The Lyapunov Exponents of Reversible Cellular Automata Are Uncomputable




AuthorsKopra J.

EditorsIan McQuillan, Shinnosuke Seki

Conference nameInternational Conference on Unconventional Computation and Natural Computation

PublisherSpringer Verlag

Publication year2019

JournalLecture Notes in Computer Science

Book title Unconventional Computation and Natural Computation : 18th International Conference, UCNC 2019, Tokyo, Japan, June 3–7, 2019, Proceedings

Journal name in sourceLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

Series titleLecture Notes in Computer Science

Volume11493

ISBN978-3-030-19310-2

eISBN978-3-030-19311-9

ISSN0302-9743

DOIhttps://doi.org/10.1007/978-3-030-19311-9_15

Self-archived copy’s web addresshttps://research.utu.fi/converis/portal/detail/Publication/41254647


Abstract

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 ϵ.


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 2024-26-11 at 12:48