Chapter 3: The World of Simple Programs

Section 8: Cyclic Tag Systems

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 - 1 elements at each step. With n=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}} and {{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]}]

gives for example the Thue-Morse substitution system {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 (Sqrt[5]-1)/2 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}}. In example (d), the frequency of 1's among the first elements of sequence is approximately 3/4; {0,0} never occurs, and the frequency of {1,1} is approximately 1/2. In example (e), the frequency of 1's is again about 3/4, but now {0,0} occurs with frequency 0.05, {1,1} occurs with frequency 0.55, while {0,0,0} and {0,1,0} cannot occur.

From Stephen Wolfram: A New Kind of Science [citation]