next up previous contents
Next: cycleor basin, Up: General properties of Previous: interpretation of graphs

the de Bruijn diagrams

Underlying the existence of the tiling is the fact that Rule 110 has semipermeable membranes. That is just a fancy way of saying that the sequence x10 always generates 1 (almost always - the ``semi'' comes from 111 0); more pertinent is that generates which is another way of characterizing the triangles. Membranes are traceable to configurations in the de Bruijn diagram. It remains to be seen how directly this membrane affects the analysis of Rule 110, even though it is an integral part of the characterization of Rule 110 by tiling.

The reason for mentioning this is that it has been known that some rules have membranes bounding macrocells, within which evolution has to seek a cycle. But not all membranes are permanent, leading to the conjecture that their dissolution might be programmed. This is an idea which has probably never been followed up, but Rule 110 may actually be an instance which fits the pattern, since the evolution depends to a certain extent on the persistence of the left margin of the triangles, and the way in which it eventually breaks up.

In honor of the role of C gliders in Cook's introduction, the dimensions of the arrays in NXLCAU21 was raised to accomodate seven generations, with the result that they are described in a diagram of 556 nodes and 705 links. It is large for the multiplicity of ways the ether background can join to the T6's which in turn join to ether or vanish. To better manage the diagram, the self-node to the quiescent state can be excised, leaving a diagram of 502 nodes and 632 links; although only a 10 stray lines from a map which is still extremely congested.

Table 2 summarizes the statistics on all the de Bruijn diagrams up to and including seven generations. The first row of each pair states the number of nodes, the second row, the number of links. When the two numbers coincide the diagram consists exclusively of loops, but not necessarily one single loop. Since zero is a quiescent state, entries of the form (1,1) indicate that it is the only configuration meeting the shifting requirement. In particular, there are no still lifes (except for zero).

The columns follow the degree of shifting, the remainder, pairs of rows, goes by generation.

 
Table 2: The number of nodes (upper number) and links (lower number) in the de Bruijn shift diagrams up to and including seven generations.  

Points of interest in the table, actually some of Cook's gliders, are the entries at (2,3) [A-gliders], at (-2.4) [B-gliders], and at (0,7) [C-gliders]. [The symbol (x,y) indicates a shift of x, negative to the left, in y generations].

Previously unreported gliders can be found at (2,5), (-1,6), and (-4,6). The (2,5) glider had already been observed in Cook's extensible gliders, but none of the three connects directly to Cook's ether.

 
Figure 11: Samples of left shifting configurations. The quiescent configuration is an implicit component of every other shift; sometimes it is the only one. Otherwise it is not shown. When there are still more components, the panel is split into horizontal slices to accomodate them.  

 
Figure 12: Periodic configurations. The quiescent configuration is an implicit component of every other shift; sometimes it is the only one. Otherwise it is not shown. When there are still more components, the panel is split into horizontal slices to accomodate them. That is not the same as a one-sided ideal, in which one single panel divides into two distinctive regions along a vertical fissure.  

 
Figure 13: Samples of right shifting configurations. The horizontal coordinate determines the shift, the vertical coordinate the number of generations which have elapsed.

The quiescent configuration is an implicit component of every other shift; sometimes it is the only one. Otherwise it is not shown.  



next up previous contents
Next: cycleor basin, Up: General properties of Previous: interpretation of graphs



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