Conserved Energy Functions for Cellular Automata:
Finding Nontrivials Faster Through a Complete Theory of the Trivials
Leemon Baird and Barry Fagin
Conserved quantities indicate fundamental physical properties of systems, and are therefore eagerly sought after in science. Conservation of energy and conservation of angular momentum, for example, are two fundamental principles that offer profound insights into the nature of the world we live in.
Cellular automata, as models of physical systems, can exhibit conserved functions of relevance to the system under study. Number conservation is a simple example, but far more sophisticated ones can be discovered with appropriate algorithmic techniques. Cellular automata with identical conserved functions are, in some sense, closely related to one another. Thus conserved functions can be used to classify cellular automata, and to identify connections between seemingly unrelated systems.
There are known algorithms to find all conserved energy functions of a given order for a given cellular automaton. They are exponentially slow, but can be made faster by eliminating the trivial conserved functions that classify all states as having the same energy. So we must find the basis set for the trivials. That problem is nontrivial.
We present here the first proofs for the basis set for all trivial conserved functions in the general case, and use this to derive a number of optimizations for reducing time and memory for the discovery of nontrivials.
We use these results to show the Game of Life has no nontrivials with any rectangular energy window containing 13 or fewer cells. Other 2D automata, however, do have nontrivials.We give the complete list of those functions for all life-like automata (i.e. 2D, 2-color, 3 × 3 neighborhood, outer totalistic) with rectangular energy windows with 9 or fewer cells, and discuss patterns we have observed.
Keywords: nontrivial, trivial, conserved, energy, function, cellular, automata, tensors, dimensions