The shift (bi-infinite) cellular automaton is a chaotic dynamical system according to all the definitions of deterministic chaos given for discrete time dynamical systems (e.g., those given by Devaney [6] and by Knudsen [10]). The main motivation to this fact is that the temporal evolution of the shift cellular automaton under finite description of the initial state is unpredictable. Even tough rigorously proved according to widely accepted formal definitions of chaos, the chaoticity of the shift cellular automaton remains quite counterintuitive and in some sense unsatisfactory. The space-time patterns generated by a shift cellular automaton do not correspond to those one expects from a chaotic process. In this paper we propose a new definition of strong topological chaos for discrete time dynamical systems which fulfills the informal intuition of chaotic behavior that everyone has in mind. We prove that under this new definition, the bi-infinite shift is no more chaotic. Moreover, we put into relation the new definition of chaos and those given by Devaney and Knudsen. In the second part of this paper we focus our attention on the class of additive cellular automata (those based on additive local rules) and we prove that essential transformations [2] preserve the new definition of chaos given in the first part of this paper and many other aspects of their global qualitative dynamics. © 1999 - Elsevier Science B. V. All rights reserved.

Cattaneo, G., Formenti, E., Margara, L., Mauri, G. (1999). On the dynamical behavior of chaotic cellular automata. THEORETICAL COMPUTER SCIENCE, 217(1), 31-51 [10.1016/S0304-3975(98)00149-2].

On the dynamical behavior of chaotic cellular automata

CATTANEO, GIANPIERO;MAURI, GIANCARLO
1999

Abstract

The shift (bi-infinite) cellular automaton is a chaotic dynamical system according to all the definitions of deterministic chaos given for discrete time dynamical systems (e.g., those given by Devaney [6] and by Knudsen [10]). The main motivation to this fact is that the temporal evolution of the shift cellular automaton under finite description of the initial state is unpredictable. Even tough rigorously proved according to widely accepted formal definitions of chaos, the chaoticity of the shift cellular automaton remains quite counterintuitive and in some sense unsatisfactory. The space-time patterns generated by a shift cellular automaton do not correspond to those one expects from a chaotic process. In this paper we propose a new definition of strong topological chaos for discrete time dynamical systems which fulfills the informal intuition of chaotic behavior that everyone has in mind. We prove that under this new definition, the bi-infinite shift is no more chaotic. Moreover, we put into relation the new definition of chaos and those given by Devaney and Knudsen. In the second part of this paper we focus our attention on the class of additive cellular automata (those based on additive local rules) and we prove that essential transformations [2] preserve the new definition of chaos given in the first part of this paper and many other aspects of their global qualitative dynamics. © 1999 - Elsevier Science B. V. All rights reserved.
Articolo in rivista - Articolo scientifico
cellular automata; chaos
English
1999
217
1
31
51
none
Cattaneo, G., Formenti, E., Margara, L., Mauri, G. (1999). On the dynamical behavior of chaotic cellular automata. THEORETICAL COMPUTER SCIENCE, 217(1), 31-51 [10.1016/S0304-3975(98)00149-2].
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10281/2536
Citazioni
  • Scopus 31
  • ???jsp.display-item.citation.isi??? 30
Social impact