Chapter 6: Starting from Randomness

Section 7: The Notion of Attractors

[State networks for] additive rules

The pictures below show networks obtained for the additive cellular automata with rules 60 and 90. The networks are highly regular and can be analyzed by the algebraic methods mentioned on page 951. The lengths of the longest cycles are given on page 951; all other cycles must have lengths which divide these. Rooted at every state on each cycle is an identical structure. When the number of cells n is odd this structure consists of a single arc, so that half of all states lie on cycles. When n is even, the structure is a balanced tree of depth 2^IntegerExponent[n, 2] and degree 2 for rule 60, and depth 2^IntegerExponent[n/2, 2] and degree 4 for rule 90. The total fraction of states on cycles is in both cases 2^-2^IntegerExponent[n, 2]. States with a single black cell are always on the longest cycles. The state with no black cells always forms a cycle of length 1.

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