Laurent Bienvenu

Can cellular automata create randomness?

Cellular automata are dynamical systems that obey a simple local rule,
which sometimes leads to a very complex global behaviour. In the
literature, the complexity of the behaviour of cellular automata has been
considered as a tool to create "randomness" (taking some complex cellular
automata as pseudo-random generators) . From a Kolmogorov complexity point
of view however, it can be shown that the Kolmogorov complexity (i.e the
randomness) of a configuration does not increase too much when transformed
via a cellular automaton, hence in that sense, it is impossible to
generate much randomness from cellular automata. We will use this simple
fact to prove results about the dynamical properties of cellular automata
as dynamical systems. If time permits, we will show that a little bit of
randomness can still be created: to wit, a non-random configuration can
have a random image by a cellular automata (this answers a question of
Calude. et al).