Notes

Chapter 2: The Crucial Experiment

Section 1: How Do Simple Programs Behave?


More general [cellular automaton] rules

The programs given so far are for cellular automata with rules of the specific kind described in this chapter. In general, however, a 1D cellular automaton rule can be given as a set of explicit replacements for all possible blocks of cells in each neighborhood (see page 60). Thus, for example, rule 30 can be given as

{{1, 1, 1} 0, {1, 1, 0} 0, {1, 0, 1} 0, {1, 0, 0} 1, {0, 1, 1} 1, {0, 1, 0} 1, {0, 0, 1} 1, {0, 0, 0} 0}

To use rules in this form, CAStep can be rewritten as

CAStep[rule_, a_List] := Transpose[{RotateRight[a], a, RotateLeft[a]}] /. rule

or

CAStep[rule_, a_List] := Partition[a, 3, 1, 2] /. rule

The rules that are given can now contain patterns, so that rule 90, for example, can be written as

{{1, _, 1} 0, {1, _, 0} 1, {0, _, 1} 1, {0, _, 0} 0}

But how can one set up a program that can handle rules in several different forms? A convenient approach is to put a "wrapper" around each rule that specifies what form the rule is in. Then, for example, one can define

CAStep[ElementaryCARule[rule_List], a_List] := rule8 - (RotateLeft[a] + 2 (a + 2 RotateRight[a]))

CAStep[GeneralCARule[rule_, r_Integer:1], a_List] := Partition[a, 2r + 1, 1, r + 1] /. rule

CAStep[FunctionCARule[f_, r_Integer:1], a_List] := Map[f, Partition[a, 2r + 1, 1, r + 1]]

Note that the second two definitions have been generalized to allow rules that involve r neighbors on each side. In each case, the use of Partition could be replaced by Transpose[Table[RotateLeft[a, i], {i, -r, r}]]. For efficiency in early versions of Mathematica, explicit rule lists in the second definition can be preprocessed using Dispatch[rules], and functions in the third definition preprocessed using Compile[{{x, _Integer, 1}}, body].

I discuss the implementation of totalistic cellular automata on page 886, and of higher-dimensional cellular automata on page 927.



Image Source Notebooks:

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