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 k^k^(2r+1) possible cellular automaton rules in all, of which k^(k^(r+1)(1+k^r)/2) are symmetric, and k^(1 + (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]