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 232 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 t2 for any rule. But without copy (fanout) operations no corresponding result is immediately clear.

Image Source Notebooks:

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