|
Articles Cellular Automata Cellular Automata as Simple Self-Organizing Systems (1982)
Cellular Automata as Simple Self-Organizing Systems (1982) |
|
One may restrict a cellular automaton to contain a finite number 
of sites (arranged, for example, on a circle). Then the total number of possible configurations in the ``phase space'' of the system is 
. Cellular automaton evolution consists in the iteration of mapping between these configurations, with each configuration tracing out a trajectory in phase space. For complex cellular automata one finds that initially nearby trajectories (corresponding to configurations differing at only a few sites) diverge exponentially with time (so that the number of differing sites increases linearly), and the mapping from initial to final configurations becomes apparently ``random'' after a few time steps (although deviations from a uniform random mapping remain).
Cellular automaton rules have the important property that they may map several initial configurations to the same final configuration, so that the corresponding trajectories merge, and microscopically irreversible time evolution occurs (1). Starting from an initial ensemble in which all possible configurations occur with equal probabilities (corresponding to complete ``disorder''), cellular automaton evolution thus irreversibly ``concentrates'' the probabilities in the ensemble into a small fraction of all the possible configurations, thereby reducing the entropy of the ensemble. The properties of these few ``attractor'' configurations (or cycles) then dominate ensemble averages, leading to statistically similar results independent of the initial state (c.f. [12]).
In a cellular automaton of finite size, every trajectory must eventually be periodic, or must merge with a periodic trajectory. In practice, the length of the ``transient'' before a trajectory merges is typically 
. The lengths of periodic cycles could in principle be 
, but in practice typically much smaller. For rules 90 and 150 (with periodic boundary conditions) one finds that all cycle lengths must divide 
where 
for 
, 
for 
, 
for 
, 
for even, and 
otherwise 
is the Euler totient function and gives the number of integers less than relatively prime to . 
, where the bound is saturated for prime, so that all cycles length 
.
The cellular automata considered here are entirely deterministic. However, simulation of some natural processes requires introduction of ``noise'' into the local rules, yielding non-deterministic cellular automata (a simple example is the Ising model at finite temperature). An arbitrarily small amount of noise prevents stable cyclic behaviour, and causes all possible states to be visited in evolution from any initial state. However, the statistical properties of structures generated in the evolution appear to degrade continuously as the intensity of noise is increased.
