next up previous
Next: The Mean-Field Refinement Up: Review of and Previous: The Parameter

Mean Field Theory

The mean field theory has mainly been used [GVK87] to characterize individual cellular automata. Here the mean field theory is used to characterize the full space of cellular automaton rules. We view the mean field theory as a parametric representation of the space of cellular automata[Gut90]. Each setting of parameter values corresponds to a subset of cellular automaton rules. As the parameter values are changed, the properties of the corresponding cellular automata change as well. The results below suggest that small changes in parameter values typically lead to small changes in the properties of the cellular automata described. At certain distinguished values of the parameters, however, changes in behavior can be abrupt.

The mean field theory describes how cellular automata act on probability measures of a particular type. A probability measure is an assignment of probability to blocks of cell states of all sizes. In empirical simulations block probabilities are estimated by the frequency with which these blocks occur in large configurations. By definition, the probability of a block b, at a given time t+1, is the sum of the probabilities of the blocks B at time t which map to b under the cellular automaton , . Let be a one-dimensional cellular automaton with radius r with two states per cell, labeled 0 and 1. If b is the cell state 1, the probability of a 1 at time t is the sum of the probabilities at time t of blocks B of length 2r+1 which lead to 1 under the rule, .

Let and denote the number of cells in state 0, 1 respectively in a block B. If we assume that the probability for a cell to be in a given state is uncorrelated with the states of other cells, then the probability of a block is just the product of the probabilities of the states of the cells in the block, . Substituting this into the above, we obtain the mean field equation

This mean field equation is a real-valued dynamical system which approximates the action of a cellular automaton on uncorrelated probability measures. In effect, the mean field theory represents the action of a cellular automaton combined with a noise process which removes all correlations between cell states after each application of the automaton.



next up previous
Next: The Mean-Field Refinement Up: Review of and Previous: The Parameter



Howard A. Gutowitz
Wed Mar 29 16:14:50 MST 1995