Chapter 9: Fundamental Physics

Section 2: The Notion of Reversibility

Numbers of reversible [cellular automaton] rules

For k=2, r=1, there are 6 reversible rules, as shown on page 436. For k=2, r=2 there are 62 reversible rules, in 20 families inequivalent under symmetries, out of a total of 2^32 or about 4 billion possible rules. For k=3, r=1 there are 1800 reversible rules, in 172 families. For k=4, r=1, some of the reversible rules can be constructed from the second-order cellular automata below. Note that for any k and r, no non-trivial totalistic rule can ever be reversible.

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