Cellular Automata

After a short introduction to cellular automata (CA), an information-theoretic analysis of one-dimensional CA is presented. It is based on a statistical or probabilistic description of the state of the cellular automaton at each time step, where the state is assumed to be an infinite sequence of symbols. Using information theory for symbol sequences, we identify the information contained in correlations, including density information, as well as the remaining randomness, the entropy of the state. We derive laws for development of the entropy over time, and we identify classes of CA dynamics for which these laws take different form: general deterministic, almost reversible, and probabilistic. A methodology for analysing changes in the probabilistic description of the CA state from one time step to the next is described in detail. Illustrations on the evolution of correlation information are given for a number of CA rules.