# Notes

## 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 ui + 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[IntegerDigits[num, k, k^Length[os]]-1 - # &, Apply[Plus, MapIndexed[k^(Length[os] - First[#2]) RotateLeft[a, #1] &, os]], {-1}]

or equivalently by

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

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