Chapter 10: Processes of Perception and Analysis

Section 11: Traditional Mathematics and Mathematical Formulas

Cellular automaton [Nand] formulas

For 1 step, the elementary cellular automaton rules are exactly the 256 n=3 Boolean functions. For 2 steps, they represent a small subset of the 2^32 n=5 functions. They require an average of about 11.6 Nand operations, and a maximum of 27 (achieved by rules 107 and 121).

For rule 254 the result after t steps (which is always asymmetric, even though the rule is symmetric) is

Nest[{{#, #[[2]] + 1}, #[[2]] + 1} &, {{1, 1}, {2, 2}}, t - 2]

If explicit copy operations were allowed, then the number of Nand operations after t steps could not increase faster than t^2 for any rule. But without copy (fanout) operations no corresponding result is immediately clear.

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