!Converted with LaTeX2HTML 95.1 (Fri Jan 20 1995) by Nikos Drakos (firstname.lastname@example.org), CBLU, University of Leeds >
There are two ways that a de Bruijn diagram can be associated with the neighborhoods of a linear cellular automaton. The neighborhoods can be attributed to the nodes or to the links. The latter is the more compact representation; then the node between two links would describe the overlapping portion of the two neighborhoods. Any classification of neighborhoods immediately becomes a classification of the links. In searching for still lifes, we would discard all those links which did not stand for a neighborhood whose central cell evolved into itself.
If the remaining links formed chains, they would be chains which remained unchanged from one generation to the next. Unless they closed into loops however, they might dwindle away in each generation. If there were suitable loops, their lengths would determine the lengths of the ring automata in which they could be found. For example, chains of alternating ones and zeroes can only be found in rings of even length according to Rule 22, whereas the zero chain can exist in rings of any length.
Consequently loops often have to be extracted from larger fragments of de Bruijn diagrams, just as they have to be to get cycles from the evolutionary diagrams; in both cases the transients leading into the loops get discarded.
The formation of barriers between macrocells is one exception to the rule that only loops give interesting still lifes. The criterion for such a barrier is that the terminal nodes have a full complement of incoming or outgoing links according to the end of the chain which they occupy.
Another combination which often occurs is that a loop will be connected through a series of links to another loop, but that there is no return path. Thus some pattern may occupy the left side of an infinite chain, then undergo a transition into another pattern which occupies the right side of the chain. Such configurations were called fuses in Gardner's column and Wainwright's newsletter, and can exist in one dimension just as well as in two.
Nor are still lifes the only patterns which can be deduced from de Bruijn diagrams. To obtain all the patterns of period two, it is only necessary to iterate the evolutionary rule once and then look for still lifes. This would transform a automaton into a automaton using a de Bruijn diagram of 4r stages, whose links would be classified by their behaviour after two generations of evolution. Similar considerations apply to periods of three or higher.
Any binary property at all of a neighborhood of cells can be reflected by its inclusion as a link in the de Bruijn diagram for neighborhoods of that length, and be extended to a larger region by pursuing chains throughout the diagram. Cells other than the central cell can repeat themselves, so that it is just as easy to search for shifting patterns as for periodic ones. Evolution into constant chains is likewise easy to test, and is helpful in determining the behaviour of backgrounds, particularly in automata with many states per cell.
Figure: Simple properties of Rule 22 via de Bruijn diagrams.
Figure shows several examples; in fact configurations possessing any of the attributes mentioned in Section , and many more, can be read off by inspection, the de Bruijn diagram being quite small.
Two less obvious properties can be mentioned. One is the search for superluminal configurations. Quiescent automata are ones in which there is a state q such that ; when such a state exists, it is generally assigned the value zero. Actually, especially for automata which are not binary, there may be several quiescent states, in which case only one of them would be labelled zero. Quiescence simply means that a non-quiet cell cannot arise unless there is another non-quiet cell in its neighborhood, which is to say, ``nearby.'' In quiescent automata information can propagate through a quiet region at a maximum velocity equal to one radius per time step; this velocity is picturesquely called the velocity of light.
A pattern can move faster than the velocity of light if it moves through a region which is densely enough populated by non-quiet cells. Superluminal configurations can always be found for any velocity, but they may turn out to be so trivial as to be uninteresting. For example, one may simultaneously be superluminal with a smaller velocity, or even be a higher harmonic of a subluminal configuration. The argument is that one can choose an arbitrary interval consisting of one super-light-second plus half the width of the neighborhood. Say its length is . Anything beyond this interval is fixed by the combination of evolution and shifting. Of course, the shifted image which emerges does not have to be part of the original interval, but there is not much else that it can be because there are only intervals and images after g generations. So, there has to be some interval which generates a recurrent pattern.
Idempotent rules lead to a particularly restrictive type of behaviour, but not all rules are idempotent. Still, one of the boolean questions which can be asked of second generation evolution is whether
and consequently whether a given rule admits any configurations which have an idempotent evolution even if all of them do not.