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 k^n possible states, but if the system has cyclic boundary conditions, then the maximum repetition period is smaller than k^n. 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_]:= k^m - 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 k^n-k. For large n, s[n, k] oscillates between about k^n-k^(n/2) and k^n-k. (See page 963.)

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