Stephen Wolfram's: A New Kind of Science | Online
Jump to Page
Look Up in Index

Chapter 6 Notes > Section 4 > Page 951 > Note (a) Previous note-----Next note
Notes for: Starting from Randomness | 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, {x^n - 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 + x^2^m) == (1 + x)^2^m 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 2^(n-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 2^(n-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.


Page image


Pages related to this note:


All notes on this page:

* Additive cellular automata [in finite regions]
* [Periods in] rules 30 and 45
* Comparison of [periods for cellular automaton] rules
* Implementing boundary conditions [in cellular automata]
* Rule 22 [with simple initial conditions]
* Rule 225 [with simple initial conditions]
* Rule 94 [with simple initial conditions]
* All notes for this section
* Downloadable programs for this page
* Downloadable images
* Search Forum for this page
* Post a comment
* NKS | Online FAQs
From Stephen Wolfram: A New Kind of Science [citation] Previous note-----Next note