On computing the Lyapunov exponents of reversible cellular automata
- PDF / 566,551 Bytes
- 14 Pages / 595.276 x 790.866 pts Page_size
- 45 Downloads / 182 Views
(0123456789().,-volV)(0123456789(). ,- volV)
On computing the Lyapunov exponents of reversible cellular automata Johan Kopra1 Accepted: 9 November 2020 The Author(s) 2020
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 d for some absolute constant d [ 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 . 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. Keywords Cellular automata Lyapunov exponents Reversible computation Computability
1 Introduction A cellular automaton (CA) is a model of parallel computation consisting of a uniform (in our case one-dimensional) grid of finite state machines, each of which receives input from a finite number of neighbors. All the machines use the same local update rule to update their states simultaneously at discrete time steps. The following question of error propagation arises naturally: If one changes the state at some of the coordinates, then how long does it take for this change to affect the computation at other coordinates that are possibly very far away? Lyapunov exponents provide one tool to study the asymptotic speeds of error propagation in different directions. The concept of Lyapunov exponents originally comes from the theory of differentiable dynamical systems, and the discrete variant of Lyapunov exponents for CA was originally defined in Shereshevsky (1992). The Lyapunov exponents of a cellular automaton F are interesting also when one considers F as a topological dynamical system, because they can be used to give an
The work was partially supported by the Academy of Finland Grant 296018 and by the Vilho, Yrjo¨ and Kalle Va¨isa¨la¨ Foundation. & Johan Kopra [email protected] 1
Department of Mathematics and Statistics, University of Turku, FI 20014 Turku, Finland
upper bound for the topological entropy of F (Tisseur 2000). It is previously known that the entropy of one-dimensional cellular automata is uncomputable (Hurd et al. 1992) (and furthermore from (Guillon and Zinoviadis 2012) it follows that there exists a single cellular automaton whose entropy is uncomputable), which gives reason to suspect that also the Lyapunov exponents are uncomputable in general. The uncomputability of Lyapunov exponents is easy to prove for (not necessarily reversible) cellular automata by using the result from Kari (1992) which says that nilpotency of cellular automata with a spreading state is undecidable. We will prove in Sect. 4 the more specific claim that the Lyapunov exponents are uncomputable even for reversible cellular automata. In the context of proving undecidabi
Data Loading...
