Notes

Chapter 5: Two Dimensions and Beyond

Section 2: Cellular Automata


General rules [for multidimensional cellular automata]

One can specify the neighborhood for any rule in any dimension by giving a list of the offsets for the cells used to update a given cell. For 1D elementary rules the list is {{-1}, {0}, {1}}, while for 2D 5-neighbor rules it is {{-1, 0}, {0, -1}, {0, 0}, {0, 1}, {1, 0}}. In this book such offset lists are always taken to be in the order given by Sort, so that for range r rules in d dimensions the order is the same as Flatten[Array[List, Table[2r + 1, {d}], -r], d - 1]. One can specify a neighborhood configuration by giving in the same order as the offset list the color of each cell in the neighborhood. With offset list os and k colors the possible neighborhood configurations are

Reverse[Table[IntegerDigits[i-1,k, Length[os]],{i,k^Length[os]}]]

(These are shown on page 53 for elementary rules and page 941 for 5-neighbor rules.) If a cellular automaton rule takes the new color of a cell with neighborhood configuration IntegerDigits[i, k, Length[os]] to be u[[i+1]], then one can define its rule number to be FromDigits[Reverse[u], k]. A single step in evolution of a general cellular automaton with state a and rule number num is then given by

Map[Part[IntegerDigits[num, k, k^Length[os]], -1-# ] &, Apply[Plus, MapIndexed[k^(Length[os] - First[#2])RotateLeft[a, #] &, os]], {-1}]

or equivalently by

Map[IntegerDigits[num, k, k^Length[os]][[-# - 1]] &, ListCorrelate[Fold[ReplacePart[k #, 1, #2 + r + 1] &, Array[0 &, Table[2r + 1, {d}]], os], a, r + 1], {d}]


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