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]