Damage Spreading and Information Distance in Cellular Automata

Abstract

Using the concept of information distance derived from Kolmogorov randomness, we study damage spreading for elementary cellular automata acting on a one-dimensional lattice. In contrast to previous definitions of the Lyapunov exponent based on Hamming distance, the new magnitude allows a better clustering of chaotic rules. The
combined use of the Lyapunov exponent, Hamming, and information distance-based, results in a more robust characterization of cellular automata behavior. An exten-sion of the type analysis shown can be directly made to other one-dimensional time and space discrete dynamical systems.