Notes

Chapter 3: The World of Simple Programs

Section 2: More Cellular Automata


Numbers of [cellular automaton] rules

Allowing k possible colors for each cell and considering r neighbors on each side, there are kk2r + 1 possible cellular automaton rules in all, of which k1/2 kr + 1(1 + kr) are symmetric, and k1 + (k - 1)(2r + 1) are totalistic. (For k = 2, r = 1 there are therefore 256 possible rules altogether, of which 16 are totalistic. For k = 2, r = 2 there are 4,294,967,296 rules in all, of which 64 are totalistic. And for k = 3, r = 1 there are 7,625,597,484,987 rules in all, with 2187 totalistic ones.) Note that for k > 2, a particular rule will in general be totalistic only for a specific assignment of values to colors. I first introduced totalistic rules in 1983.

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