A4 Article in conference proceedings

The Lyapunov Exponents of Reversible Cellular Automata Are Uncomputable




List of Authors: Kopra J.

Conference name: International Conference on Unconventional Computation and Natural Computation

Publisher: Springer Verlag

Publication year: 2019

Journal: Lecture 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 source: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

Title of series: Lecture Notes in Computer Science

Volume number: 11493

ISBN: 978-3-030-19310-2

eISBN: 978-3-030-19311-9

ISSN: 0302-9743

DOI: http://dx.doi.org/10.1007/978-3-030-19311-9_15


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 2021-24-06 at 08:34