It is not surprising that the reasons for studying automata change from
time to time, and that the amount of detail required keeps increasing.
Basically a cellular automaton is a lattice formed from cells, each of
which has k states, conveniently numbered from 0 to kkkkkkkkkkkkkkk-111111111111111. As a
consequence of forming part of the lattice, each cell may be associated
with several nearby cells, which form its neighborhood. The geometrical
shape of the neighborhood may vary, but typically only the closest
neighbors up to some radius r are included. Neighborhoods are
supposed to have the same form for all cells, and are therefore
translates of one another. Consequently there is a single function
to specify the state of a cell at the next generation in
terms of the states of its neighbors (generally including itself) in
the present generation.
Although relates cells to neighborhoods, its systematic
application throughout the lattice defines a mapping
from the
configuration---assignment of states to lattice sites---of the
automaton in one generation to that of the next. Of course, the central
problem of the theory of cellular automata is obtaining a satisfactory
description of
.
If an automaton, such as von Neumann's universal constructor, had been
carefully constructed to serve a special purpose, the greatest interest
in its operation would naturally lie in whether it performed according
to specification or not. On the other hand, if an arbitrary automaton
were presented for examination, the most natural reaction would be to
observe the course of a typical evolution, that is, the result of
repeated iteration of . Different concepts of ``typical'' would be
likely to produce somewhat different results. The initial configuration
might be a simple pattern, such as a group of cells in one state with
the remainder in another. Alternatively, some short sequence of cell
states might be repeated indefinitely, giving a periodic initial
configuration. If still greater variety were desired, the states of the
individual cells might be assigned with the help of a random number
generator.
The best way to reach a compromise between finite and infinite automata would be to combine the second alternative with the third. But then one would soon find that mappings of finite sets into themselves have one fundamental property which turns up over and over again in practically any context whatsoever. Their iterations must eventually become periodic. Evolution being the pertinent mapping for cellular automata, the inescapable conclusion is that the sequence of configurations through which the automaton evolves must eventually become cyclic, oftentimes even static. Thus one is advised to begin the analysis of an automaton by ascertaining all of its periods, both temporal and spatial.
Knowing whether an automaton is large enough to be considered infinite, distinguishing between periodic and aperiodic extensions, and resolving other philosophical dilemmas have a practical importance. Recognizing an entity such as the square root of two so that the diagonal of the unit square can have a length only requires that that such a number can be represented to an arbitrary accuracy. Likewise, although a Turing machine must never be denied additional tape, a generous allotment might suffice for all the calculations required by some project. Thus it is convenient to work with finite structures in such a way that their scale does not have to be stated explicitly, making them implicitly infinite. It then remains to identify any additional structure which may have inadvertently been introduced.
Describing the asymptotic behavior of infinite, but not periodic, configurations within an automaton is a relatively recent development, much of whose motivation arises from trying to identify the computational powers of automata. At the same time, it has been realized that the transient portion of their evolution, particularly when it persists for an exceptionally long time, is not entirely uninteresting, and that its statistical properties warrant investigation. Also, there is interest in locating some or all of the cycles without the necessity of performing all the trial evolutions, the possibility of which is part of the theory of computational complexity.
Whatever the degree of sophistication of the presentation, it is not likely that one is going to find a discussion of a cellular automaton which omits all reference to its periodicity, from its static configurations onward.