Julien Cervelle, Bruno Durand, Enrico Formenti

Algorithmic Information Theory and Cellular Automata Dynamics

Abstract:

We study the ability of discrete dynamical systems to transform/generate randomness in cellular spaces. Thus, we endow the space of bi-infinite words by a metric inspired by information distance (defined in the context of Kolmogorov complexity or algorithmic information theory). We prove structural properties of this space (such as non-separability, completness, prefectness and infinite topological dimnension), which turn usefull to understand the transformation of information performed by dynamical systems evolving on it. Finally, we focus on cellular automata and prove a dichotomy theorem: continuous cellular automata are either equivalent to the identity or to a constant one. This means that they cannot produce any amount of randomness.