Complex Systems

On the Entropy Geometry of Cellular Automata Download PDF

John Milnor
Institute for Advanced Study, Princeton University,
Princeton, NJ 08540, USA


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.