
On the Entropy Geometry of Cellular Automata
John Milnor
Institute for Advanced Study, Princeton University,
Princeton, NJ 08540, USA
Abstract
We consider configurations which assign some elements of a fixed finite alphabet to each point of an -dimensional lattice. An
-dimensional cellular automaton map assigns a new configuration
to each such configuration
, in a translation invariant manner, and in such a way that the values of
throughout any finite subset of the latice depend only on the values of
throughout some larger finite subset. If we iterate such a map
over and over, then the complete history of the resulting configurations throughout time can be described as a new configuration over an
-dimensional "space-time" lattice. This note will describe the distribution and flow of information throughout this
-dimensional lattice by introducing an
-dimensional entropy function which measures the density of information in very large finite sets.