cycle, or basin, diagrams

Continuing the listing of de Bruijn diagrams by looking at cycle diagramscycle diagram doesn't turn up much beyond what is already in Wuensche and Lesser's Atlas [11]; in fact after increasing the arrays in LCAU they now cover the same range.

Table 1.6: Number of configurations of given cycle and period.

p/c	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1
2	.	.	.	2	.	.	.	2	.	.	.	2	.	.	.	2
3	x	.	.	.	.	.	.	.	3	.	.	.	.	.	.	.
4	x	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.
5	x	x	.	.	.	.	.	.	.	3	.	.	.	.	.	.
6	x	x	.	.	.	.	.	.	.	.	.	.	.	.	.	.
7	x	x	.	.	.	.	.	.	9	.	11	.	.	.	.	2
8	x	x	.	.	.	.	.	1	.	.	.	.	.	.	.	.
9	x	x	x	.	.	2	.	.	.	.	.	6	.	.	.	.
10	x	x	x	.	.	.	.	.	.	.	.	.	.	.	.	.
11	x	x	x	.	.	.	.	.	.	.	.	.	.	.	.	.
12	x	x	x	.	.	.	.	.	.	.	.	.	.	7	.	.
13	x	x	x	.	.	.	.	.	.	.	.	.	.	.	.	.
14	x	x	x	.	.	.	1	.	.	.	.	.	.	1	.	.
15	x	x	x	.	.	.	.	.	.	2	.	.	.	.	.	.
16	x	x	x	.	.	.	.	2	.	.	.	.	.	.	.	2

The x's in Table 1.6 mark unavailable periods, but the limit to the lengths of periods increases exponentially leaving little point to trying to incorporate this detail into the table. Equally, there is an exponential limit to the lengths of prime cycles running across columns, to be noted alongside the fact that multiples of periods are periods.

Table 1.7: Long periods up to cycle length 16.

cycle	period	multiplicity
10	25	2
11	110	1
12	18	2
13	351	1
14	21	2
14	91	2
15	295	3
16	24	6
16	32	3

Amongst these first sixteen cycle lengths are some which have periods too long for inclusion in Table 1.6; they are listed in Table 1.7.

But in both the de Bruijn diagrams and the basin diagrams there is an interesting item of note, the short height of the basin of attraction for the quiescent state (0, that is), which doesn't pass 9 and is frequently shorter.

The basin diagram for zeroes is cummulative, since anything which evolves to zero stays zero. But since a line of ones is the only alternative, it is interesting to see what produces ones for each ring circumference. That is where the small height is noticeable.

Table 1.8: summary of the structure of the cycle diagrams for evolution to the constant value 0.

cycle	mass	max height
2	4	2
3	8	3
4	4	2
5	32	5
6	10	3
7	9	2
8	20	3
9	17	3
10	134	9
11	35	3
12	34	3
13	54	3
14	67	3
15	113	5

Note that cycles of length 10 seem to be favored. That also shows up in the de Bruijn diagrams for evolution to the constant value 1:

Table 1.9: summary of the structure of the de Bruijn diagrams for evolution to the constant value 1.

generation	nodes	links	comment
2	3	4	2-cycle fused with 3-cycle
3	7	8	3-cycle having common vertex with 5-cycle
4	16	18	2 5-cycles, one way connection in 2 places
5	33	38	cycles 5-5-13 all interlinked
6	10	10	single cycle length 10
7	32	34	10-cycle intercommunicates with another
8	38	40	2 10-cycles attached to a 20-cycle
9	81	90	several interlinked cycles
10	0	0	empty diagram

Upon further analysis it appears that the largest triangle which can possibly emerge from the evolutionary process is T42. Of course, larger triangles could be specified as part of an initial configuration, but otherwise they belong to a multiple generation Garden of Eden. Even so, the level ten de Bruijn diagram for evolution to 1 shows that up to ten generations, triangles of any size can be prearranged. The interest in the synthesis of T23 lies in the fact that, as a result of a composite glider collision of a D, a C2, and a packet of four B's, there is no limit to the delay that could be incurred while waiting for one of them to appear.

Figure 1.22: The de Bruijn diagram for evolution to the constant 1 after six generations.

Figure 1.23: The de Bruijn diagram for evolution to the constant 1 after eight generations.

The de Bruijn diagram for evolution to the constant value 1 in nine generations is empty, which simply means that the diagram is acyclic, and its nucleus is empty. The full, unlabelled de Bruijn diagram has a quarter million nodes with half a million links. Appproximately half of these evolve to a single 1, of which another half can join with another link to produce a pair of 1's. Actually the percentage remains as high as a half but briefly, drops down to the order of ten percent, and continues to diminish. Altogether, a dozen or two chains remain, overlapping to a degree, with a length of 44 1's.

Since the resultant figure is acyclic, and there are two less 0's in the next generation than there were 1's in the current generation, T42 is the largest emergent tile. Of course, the initial configuration could have arbitrarily long strings of zeroes, whose remnants would still be encountered until the left expansivity of the right margin closed them off.

Except for the fact that the de Bruijn diagram is already quite large, graphs for additional generations could be examined to see whether the necessarily acyclic graphs would have even shorter transients, thereby limiting still further the maximum size of emergent tiles. Working from the opposite direction, finding initial conditions such as the proper positioning of gliders for a future collision, would establish lower limits to the size of emergent tiles.

Figure 1.24: One of the largest triangles whose emergence has been observed is the T23. Left: construction by electronic quadrille paper. Right: verification by computer simulation.

Figure 1.25: Large triangles are correspondingly rare, but many of them can be found by systematic search. Some are collision products, which means that they can be formed at arbitrary late times. Others are decomposition products in lattice interfaces, while still others just appear, without having any clear origin.