|
Articles Mathematics Algebraic Properties of Cellular Automata (1984)
Algebraic Properties of Cellular Automata (1984) |
|
We consider first the formulation for one-dimensional cellular automata in which the evolution of a particular site depends on its own value and those of its nearest neighbours. Section 4 generalizes the formalism to several dimensions and more neighbours.
We take the cellular automaton to consist of 
sites arranged around a circle (so as to give periodic boundary conditions). The values of the sites at time step 
are denoted 
. The possible site values are taken to be elements of a finite commutative ring 
with 
elements. Much of the discussion below concerns the case 
, in which site values are conveniently represented as integers modulo . In the example considered in Sect. 3, 
, and each site takes on a value 0 or 1.
The complete configuration of a cellular automaton is specified by the values of its sites, and may be represented by a characteristic polynomial (generating function) (cf. [2], [3])
where the value of site 
is the coefficient of 
, and all coefficients are elements of the ring . We shall often refer to configurations by their corresponding characteristic polynomials.
It is often convenient to consider generalized polynomials containing both positive and negative powers of 
: such objects will be termed ``dipolynomials''. In general, 
is a dipolynomial if there exists some integer 
such that 
is an ordinary polynomial in . As discussed in Appendix A, dipolynomials possess divisibility and congruence properties analogous to those of ordinary polynomials.
Multiplication of a characteristic polynomial 
by 
yields a dipolynomial which represents a configuration in which the value of each site has been transferred (shifted) to a site 
places to its right (left). Periodic boundary conditions in the cellular automaton are implemented by reducing the characteristic dipolynomial modulo the fixed polynomial 
at all stages, according to
Note that any dipolynomial is congruent modulo 
to a unique ordinary polynomial of degree less than .
In general, the value 
of a site in a cellular automaton is taken to be an arbitrary function of the values 
, 
, and 
at the previous time step. Until Sect. 5, we shall consider a special class of ``additive'' cellular automata which evolve with time according to simple linear combination rules of the form (taking the site index modulo )
where the 
are fixed elements of , and all arithmetic is performed in . This time evolution may be represented by multiplication of the characteristic polynomial by a fixed dipolynomial in 
,
according to
where arithmetic is again performed in . Additive cellular automata obey an additive superposition principle which implies that the configuration obtained by evolution for time steps from an initial configuration 
is identical to 
, where 
and 
are the results of separate evolution of 
and 
, and all addition is performed in . Since any initial configuration can be represented as a sum of ``basis'' configurations 
containing single nonzero sites with unit values, the additive superposition principle determines the evolution of all configurations in terms of the evolution of 
. By virtue of the cyclic symmetry between the sites it suffices to consider the case 
.
