|
Cellular Automata (1983) |
|
The cellular automaton rule of Eq. 1 is particularly simple and admits a rather complete mathematical analysis.
The fractal patterns of Figs. 2 and 3 may be characterized in a simple algebraic manner. If no reduction modulo 2 were performed, then the values of sites generated from a single nonzero initial site would simply be the integers appearing in Pascal's triangle of binomial coefficients. The pattern of nonzero sites in Figs. 2 and 3 is therefore the pattern of odd binomial coefficients in Pascal's triangle. (See Stephen Wolfram, ``Geometry of Binomial Coefficients,'' to be published in American Mathematical Monthly.)
This algebraic approach may be extended to determine the structure of the state transition diagram of Fig. 6. (See O. Martin, A. Odlyzko, and S. Wolfram, ``Algebraic Properties of Cellular Automata,'' Bell Laboratories report (January 1983) and to be published in Communications in Mathematical Physics.) The analysis proceeds by writing for each configuration a characteristic polynomial
where 
is a dummy variable, and the coefficient of 
is the value of the site at position 
. In terms of characteristic polynomials, the cellular automaton rule of Eq. 1 takes on the particularly simple form
where
and all arithmetic on the polynomial coefficients is performed modulo 2. The reduction modulo 
implements periodic boundary conditions. The structure of the state transition diagram may then be deduced from algebraic properties of the polynomial 
. For even 
one finds, for example, that the fraction of states on attractors is 
, where 
is defined as the largest integral power of 2 that divides 
(for example, 
).
Since a finite cellular automaton evolves deterministically with a finite total number of possible states, it must ultimately enter a cycle in which it visits a sequence of states repeatedly. Such cycles are manifest as closed loops in the state transition graph. The algebraic analysis of Martin et al. shows that for the cellular automaton of Eq. 1 the maximal cycle length 
(of which all other cycle lengths are divisors) is given for even by
or
For odd , may be shown to divide
and in fact is almost always equal to this value (the first exception occurs for 
). Here 
is a number theoretical function defined to be the minimum positive integer 
for which 
modulo . The maximum value of , typically achieved when is prime, is 
. The maximal cycle length is thus of order 
, approximately the square root of the total number of possible states 
.
An unusual feature of this analysis is the appearance of number theoretical concepts. Number theory is inundated with complex results based on very simple premises. It may be part of the mathematical mechanism by which natural systems of simple construction yield complex behavior.
