Next: Ancestors Up: What to look Previous: Cycles

Periods

The rows of the period-cycle table can be found from de Bruijn diagrams in the same way that the cycles can be found from the evolution diagram; since 2r+1 cells are needed to deduce a generation of evolution, only about half as many periods as cycles can be worked out for a given amount of effort. This anomaly is really an artifact of the way r parameterizes the neighborhood, and would disappear if half-integral increments were taken for r.

Similar theoretical conclusions are possible, since the periods are gotten from a subset of the de Bruijn diagram. A 2r-stage de Bruijn diagram for k symbols has nodes; k times as many links. Once this number of links has been used up in constructing a path through the diagram, one of them would have to be repeated. Thus there is also an exponential upper bound in the rows of the period-cycle table. For example, if an automaton has a cycle of period 2, it must already show up in some short ring; if it has not appeared in rings below a certain limit, it will never appear in longer rings.

Similar statistics can be compiled for the de Bruijn diagrams: the number of periods and their lengths, the number of transients leading into loops, and the corresponding convergence and divergence factors. Failed loops are still interesting; they correspond to strings which are periodic, but which dwindle away with each generation, eventually leaving a residue which is no longer periodic.

Both the cycle diagrams and the period diagrams may have intersecting loops; this simply means that choices are present at certain junctures in working up a chain of cells with a certain property, leading to a greater variety of sequences than would otherwise occur. This choice is particularly vivid in the de Bruijn diagram when one of the loops consists of a single node of identical cells embedded in another loop, since these can be strings of Wolfram's Class IV.

Not only can the de Bruijn diagram can be used to reveal the periodicities of a given cellular automaton, it can also be used in automaton synthesis. That is, desired loops can be marked out first in the diagram, and then a rule chosen which respects the links. For period 1 properties the mapping has to be direct, since each link in the de Bruijn diagram corresponds to a distinct neighborhood in the automaton. Including or excluding it from the period diagram either determines or limits the value of the transition for that neighborhood. For longer periods the evolution corresponds to a composite rule, which may or may not be factorizable in the required manner.

Next: Ancestors Up: What to look Previous: Cycles

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