next up previous contents
Next: Ancestors Up: The collection LCAU Previous: Probability

De Bruijn diagrams

With time, the evolution of finite automata becomes periodic; automata whose lattice is a ring or a torus already fit this description, although the length of the period may be extremely long, as well as the time required to pass through the transients and arrive at the final cycle.

The systematic way to decide upon the periodic behavior of a cellular automaton is to use de Bruijn diagrams, which are simply maps showing the relation of neighborhoods to one another, annotated with details concerning interesting aspects of their evolution. All the LCAU programs contain a submenu devoted to the calculation of de Bruijn diagrams.

For neighborhoods of large radii or automata of numerous states, the quantity of information obtainable (or rather, the range of parameters over which it is available, the quantity actually remaining fairly constant) diminishes. Therefore the coverage is more complete for the smaller automata.

For two dimensions and beyond, the quantity of computation required is truly formidable.



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