Notes

Chapter 6: Starting from Randomness

Section 4: Systems of Limited Size and Class 2 Behavior


Additive cellular automata [in finite regions]

In the case of additive rules such as rule 90 and rule 60, a mathematical analysis of the repetition periods can be given (as done by Olivier Martin, Andrew Odlyzko and me in 1983). One starts by converting the list of cell colors at each step to a polynomial FromDigits[list, x]. Then for the case of rule 60 with n cells and cyclic boundary conditions, the state obtained after t steps is given by

PolynomialMod[(1 + x)t z, {xn - 1, 2}]

where z is the polynomial representing the initial state, and z = 1 for a single black cell in the first position. The state z = 1 evolves after one step to the state z = 1 + x, and for odd n this latter state always eventually appears again. Using the result that (1 + x2m) (1 + x)2m modulo 2 for any m, one then finds that the repetition period always divides the quantity p[n]=2^MultiplicativeOrder[2, n] - 1, which in turn is at most 2n-1-1. The actual periods are often smaller than p[n], with the following ratios occurring:

There appears to be no case for n>5 where the period achieves the absolute maximum 2n-1-1.

In the case of rule 90 a similar analysis can be given, with the 1 + x used at each step replaced by 1/x + x. And now the repetition period for odd n divides

q[n]=2^MultiplicativeOrder[2, n, {1,-1}] - 1

The exponent here always lies between Log[k, n] and (n-1)/2, with the upper bound being attained only if n is prime. Unlike for the case of rule 60, the period is usually equal to q[n] (and is assumed so for the picture on page 260), with the first exception occurring at n=37.

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