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] := rule[[ 8 - (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.

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