We apply the two different definitions of chaos given by Devaney and by Knudsen for general discrete time dynamical systems (DTDS) to the case of elementary cellular automata, i.e., 1-dimensional binary cellular automata with radius 1. A DTDS is chaotic according to the Devaney's definition of chaos iff it is topologically transitive, has dense periodic orbits, and it is sensitive to initial conditions. A DTDS is chaotic according to the Knudsen's definition of chaos iff it has a dense orbit and it is sensitive to initial conditions. We enucleate an easy-to-check property (left or rightmost permutivity) of the local rule associated with a cellular automaton which is a sufficient condition for D-chaotic behavior. It turns out that this property is also necessary for the class of elementary cellular automata. Finally, we prove that the above mentioned property does not remain a necessary condition for chaoticity in the case of non elementary cellular automata. © 2000 Published by Elsevier Science B.V. All rights reserved.

Cattaneo, G., Finelli, M., Margara, G. (2000). Investigating topological chaos by elementary cellular automata dynamics. THEORETICAL COMPUTER SCIENCE, 244, 219-241 [10.1016/S0304-3975(98)00345-4].

Investigating topological chaos by elementary cellular automata dynamics

CATTANEO, GIANPIERO;
2000

Abstract

We apply the two different definitions of chaos given by Devaney and by Knudsen for general discrete time dynamical systems (DTDS) to the case of elementary cellular automata, i.e., 1-dimensional binary cellular automata with radius 1. A DTDS is chaotic according to the Devaney's definition of chaos iff it is topologically transitive, has dense periodic orbits, and it is sensitive to initial conditions. A DTDS is chaotic according to the Knudsen's definition of chaos iff it has a dense orbit and it is sensitive to initial conditions. We enucleate an easy-to-check property (left or rightmost permutivity) of the local rule associated with a cellular automaton which is a sufficient condition for D-chaotic behavior. It turns out that this property is also necessary for the class of elementary cellular automata. Finally, we prove that the above mentioned property does not remain a necessary condition for chaoticity in the case of non elementary cellular automata. © 2000 Published by Elsevier Science B.V. All rights reserved.
Articolo in rivista - Articolo scientifico
investigating, topological, chaos, elementary, cellular, automata, dynamics
English
219
241
Cattaneo, G., Finelli, M., Margara, G. (2000). Investigating topological chaos by elementary cellular automata dynamics. THEORETICAL COMPUTER SCIENCE, 244, 219-241 [10.1016/S0304-3975(98)00345-4].
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/20510
Citazioni
  • Scopus 42
  • ???jsp.display-item.citation.isi??? 37
Social impact