de Bruijn diagram
A de Bruijn diagram is a graph used in the study of cellular automata, wherein the nodes represent neighborhood fragments and the links represent the full neighborhood. Normally fragments are chosen as the intersection of two adjacent neighborhoods, chains of links then representing elongated configurations. Not only do the links define neighborhoods, they can be labelled by some property of the neighborhood:
- the central cell of the neighborhood, or
- the cell to which the neighborhood evolves, or even
- a boolean value expressing some property of the neighborhood:
- the new cell always enters the same state, e.g., vanishing
- still life: the neighborhood evolves to its central cell
- shift: the new cell always matches a specific neighbor.
If the nodes encompass sufficiently more than a single neighborhood, for example a two-generation neighborhood, the label can measure periodicity as well as shifting. In any event, the result depicts the evolution of an arbitrarily extended configuration at a fixed stage of evolution. The de Bruijn diagram will be finite because there will be only finitely many fragments for a given number of states and size of neighborhood. Therefore they contain trees rooted on cycles, leaves revealing fragments that cannot be matched according to the given labelling. Full, unlabelled, diargams are extremely regular.
De Bruijn diagrams for one dimensional cellular automata were used in electronics and cryptography to describe shift register sequences; but they had an earlier history in recreational mathematics as the schoolgirls problem. With higher dimensional automata, the overlapping and adjacency of neighborhoods is much more complicated, making it desirable to attack their construction in stages. First, a linear, one dimensional sequence of neighborhoods is treated as though it were one dimensional. Inherent overlap and subsequent labelling according to internal relations between the neighbors renders this possible.
Its de Bruijn diagram reveals possible ripples, or rather, possible single strands. At the second stage, these strands are stacked into a plane. To avoid working with infinitely long strands, the first level diagram is consulted to find the cycles of a particular length; only those are used to build a cylinder. The process could be repeated for further dimensions, but for the Game of Life, two is sufficient.
Life has a pervasive vacuum, represented at the first level diagram by a pack of zeroes. Choosing only cycles taken from the component of those zeroes, the second stage produces freestanding configurations whose width is that of the circumference of the cylinder. Nevertheless, the cylinder would still be infinitely long. Cycles still connected to the zero node would generate finite objects. If several such cycles were interconnected, many fairly intricate families could result, whose complexity would depend on choices amongst multiple links from a node; a perfect opportunity for a random walk.
See also
External links
- de Bruijn graph at the Life Lexicon