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 (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.

Image Source Notebooks:

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