next up previous
Next: Self-reproducing automata Up: What has been Previous: The concept of

The evolution of finite systems into cycles

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.



next up previous
Next: Self-reproducing automata Up: What has been Previous: The concept of



Harold V. McIntosh
E-mail:mcintosh@servidor.unam.mx