Thus for example f[g][x] , f[g[h]][x] and f[g][h][x] are all possible expressions. … (In principle one can imagine representing all objects with forms such as f[x, y] by so-called currying as f[x][y] , and indeed I tried this in the early 1980s in SMP.

Such systems are like cellular automata on networks, except for the fact that when they are set up each node has a rule that is randomly chosen from all 2 2 s possible ones with s inputs. … Note that in almost all work on random Boolean networks averages are in effect taken over possible configurations, making it impossible to see anything like the kind of complex behavior that I discuss in cellular automata and many other systems in this book.

Most such rules eventually end up involving meaningless quantities such as f[0] and f[–1] , but the particular rules shown here all avoid this problem.

On a two-dimensional grid one can certainly imagine snaking backwards and forwards or spiralling outwards to scan all the elements.

And in fact, in general the simple cellular automaton shown below seems remarkably successful at reproducing all sorts of obvious features of snowflake growth.

For even though this pattern is produced by a simple one-dimensional cellular automaton rule, and even though one can see by eye that it contains at least some small-scale regularities, none of the schemes we have discussed up till now have succeeded in compressing it at all.

The system generates a dark gray stripe on the left at all positions that correspond to any product of numbers other than 1.

But for underlying rules that have more complex behavior—like rules 22, 30, or 110—it turns out that in the end it is always possible to emulate all 256 elementary rules.

A simple statement in predicate logic is ∀ x ( ∀ y x  y) ∨ ∀ x ( ∃ y ( ¬ x  y)) , where ∀ is "for all" and ∃ is "there exists" (defined in terms of ∀ on page 774 )—and this particular statement can be proved True from the axioms. … In basic logic any statement that is true for all possible assignments of truth values to variables can always be proved from the axioms of basic logic. In 1930 Kurt Gödel showed a similar result for pure predicate logic: that any statement that is true for all possible explicit values of variables and all possible forms of predicates can always be proved from the axioms of predicate logic.

Indeed, in the networks shown there all the nodes on each row are in effect connected in parallel to the nodes on the row below. … The other rules shown do not, however, suffer from this problem: in all of them progressively more points are reached in space as time goes on.