Notes

Chapter 2: The Crucial Experiment

Section 1: How Do Simple Programs Behave?


Mathematical interpretation of cellular automata

In the context of pure mathematics, the state space of a 1D cellular automaton with an infinite number of cells can be viewed as a Cantor set. The cellular automaton rule then corresponds to a continuous mapping of this Cantor set to itself (continuity follows from the locality of the rule). (Compare page 959.)

The pictures above show representations of the mappings corresponding to various rules, obtained by plotting Sum[a[t+1, i] 2^-i, {i, -n, n}] against Sum[a[t, i] 2^-i, {i, -n, n}] for all possible choices of the a[t, i]. (Periodic boundary conditions are used, so that the a[t,i] can be viewed as corresponding precisely to digits of rational numbers.) Rule 170 is the classic shift map which shifts all cell values one position to the left without changing them. In the pictures below, this map has the form Mod[2x, 1] (compare page 153).


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