next up previous
Next: References Up: What Has and What Previous: Practical applications

Conclusion

With any body of knowledge, there is a set of definitions and axioms, followed by a series of results---the theorems. One would like to know that the basic assumptions lead to a well defined structure which then exhibits certain remarkable characteristics which set it apart from other structures.

In the case of cellular automata, the definitions lead first to the association of ``cells'' with ``neighborhoods'' via a function defining cellular evolution. Then the association is repeated uniformly throughout some lattice, leading to the function mapping configurations from one to another, and thus the evolution of the lattice. The theory of cellular automata is essentially the theory of the interrelation of these two functions, and especially the behavior of under iteration.

In the forward direction, the theorems relate to the limit sets of the evolution, including the rate at which limits are approached and the nature of the limiting configurations, often from the point of view of formal language theory. ``Crystallographic'' limits, cyclic or shifting in space and periodic in time, are of a particular practical interest; de Bruijn diagrams lead directly to their determination in the great majority of cases. Theoretically and philosophically important are the aperiodic limits, particularly those whose linguistic description is especially complex. In this latter category may be included the universal constructors of von Neumann, the emulators of Turing machines, and the like.

In the backward direction, the overlapping of neighborhoods allowed Moore to prove the Garden of Eden theorem, which does not apply to arbitrary mappings.

The existence of a probability measure compatible with permits the calculation of equilibrium frequencies and entropies for the lattice and so is an important adjunct to itself; consequently the determination of either or reasonable approximations thereto play an important role in theory of cellular automata.

Finally, the existence of an extensive collection of well studied examples is a delightful part of the theory, particularly because many of them have proved to have a considerable entertainment value.



next up previous
Next: References Up: What Has and What Previous: Practical applications



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