Properties [of cyclic tag systems]
Assuming that black and white elements occur in an uncorrelated way, then the sequences in a cyclic tag system with n blocks should grow by an average of Count[Flatten[rules], 1]/n - 1Count[Flatten[rules], 1]/n - 1
elements at each step. With n = 2n = 2
blocks, this means that growth can occur only if the total number of black elements in both blocks is more than 3. Rules such as {{1, 0}, {0, 1}}{{1, 0}, {0, 1}}
and {{1, 1}, {0}}{{1, 1}, {0}}
therefore yield repetitive behavior with sequences of limited length.
Note that if all blocks in a cyclic tag system with n blocks have lengths divisible by n, then one can tell in advance on which steps blocks will be added, and the overall behavior obtained must correspond to a neighbor-independent substitution system. The rules for the relevant substitution system may however depend on the initial conditions for the cyclic tag system.
Flatten[{1, 0, CTList[{{1, 0, 0, 1}, {0, 1, 1, 0}}, {0, 1}, t]}]Flatten[{1, 0, CTList[{{1, 0, 0, 1}, {0, 1, 1, 0}}, {0, 1}, t]}]
gives for example the Thue–Morse substitution system {1 {1, 0}, 0 {0, 1}}{1 {1, 0}, 0 {0, 1}}
.
In example (a), the elements are correlated, so that slower growth occurs than in the estimate above. In example (c), the elements are again correlated: the growth is by an average of (√5 - 1)/2 ≃ 0.618(\!\(\*SqrtBox[\(5\)]\)-1)/2\[TildeEqual]0.618
elements at each step, and the first elements on alternate steps form the same nested sequence as obtained from the substitution system {1 {1, 0}, 0 {1}}{1 {1, 0}, 0 {1}}
. In example (d), the frequency of 1's among the first elements of sequence is approximately 3/4; {0, 0}{0, 0}
never occurs, and the frequency of {1, 1}{1, 1}
is approximately 1/2. In example (e), the frequency of 1's is again about 3/4, but now {0, 0}{0, 0}
occurs with frequency 0.05, {1, 1}{1, 1}
occurs with frequency 0.55, while {0, 0, 0}{0, 0, 0}
and {0, 1, 0}{0, 1, 0}
cannot occur.