The picture below shows some examples of the results. And once again what we see is that for rules with fairly simple behavior the formulas are usually fairly simple. But in cases like rule 30, the formulas one gets are already quite complicated even after just two steps.


Minimal representations in terms of Nand functions of the first two steps in the evolution of the same cellular automata as on the facing page. In each case, the network and formula shown are ones that involve the absolute minimum number of operations. Finding these effectively required searching through billions of possibilities. The picture at the top left shows the action of a single Nand function. The next three pictures show how the operations used in DNF formulas can be built up from Nands.

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