|
Articles General Interest Cellular Automata as Models of Complexity (1984)
Cellular Automata as Models of Complexity (1984) |
|
Most cellular automaton rules have the important feature of irreversibility: several different configurations may evolve to a single configuration, and, with time, a contracting subset of all possible configurations appears. Starting from all possible initial configurations, the cellular automaton evolution may generate only special `organized' configurations, and `self-organization' may occur.
For class I cellular automata, essentially all initial configurations evolve to a single final configuration, analogous to a limit point in a continuous dynamical system. Class 2 cellular automata evolve to limit sets containing essentially only periodic configurations, analogous to limit cycles. Class 3 cellular automata yield chaotic aperiodic limit sets, containing analogues of chaotic or `strange' attractors.
Entropies and dimensions give a generalized measure of the density of the configurations generated by cellular automaton evolution. The (set) dimension or limiting (topological) entropy for a set of cellular automaton configurations is defined as (compare ref. [14])
where 
gives the number of distinct sequences of 
site values that appear. For the set of possible initial configurations, 
. For a limit set containing only a finite total number of configurations, 
. For most class 3 cellular automata, 
decreases with time, giving, 
, and suggesting that a fractal subset of all possible configurations occurs.
A dimension or limiting entropy 
corresponding to the time series of values of a single site may be defined in analogy with equation (2). (The analogue of equation (2) for a sufficiently wide patch of sites yields atopologically-invariant entropy for the cellular automaton mapping.) 
for periodic sets of configurations.
and may be modified to account for the probabilities of configurations by defining
and its analogue, where 
are probabilities for possible length sequences. These measure dimensions may be used to delineate the large time behaviour of the different classes of cellular automata:
As discussed below, dimensions are usually undefined for class 4 cellular automata.
