Chapter 6: Starting from Randomness

Section 4: Systems of Limited Size and Class 2 Behavior

Maximum periods [in cellular automata]

A cellular automaton with n cells and k colors has kn possible states, but if the system has cyclic boundary conditions, then the maximum repetition period is smaller than kn. The reason is that different states of the cellular automaton have different symmetry properties, and thus cannot be on the same cycle. In particular, if a state of a cellular automaton has a certain spatial period, given by the minimum positive m for which RotateLeft[list, m]==list, then this state can never evolve to one with a larger spatial period. The number of states with spatial period m is given by

s[m_, k_]:= km - Apply[Plus, Map[s[#, k] &, Drop[Divisors[m], -1]]]

or equivalently

s[m_, k_]:=Apply[Plus, (MoebiusMu[m/#] k^#)&[Divisors[m]]]

In a cellular automaton with a total of n cells, the maximum possible repetition period is thus s[n, k]. For k=2, the maximum periods for n up to 10 are: {2, 2, 6, 12, 30, 54, 126, 240, 504, 990}. In all cases, s[n, k] is divisible by n. For prime n, s[n, k] is kn-k. For large n, s[n, k] oscillates between about kn-k^(n/2) and kn-k. (See page 963.)

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