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 de Bruijn 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 vertes 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	10	10	single cycle length 10
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.20: The de Bruijn diagram for evolution to the constant 1 after seven generations.

  

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