Growth rates [of functions] One can characterize most functions by their ultimate rates of growth. … To go further one begins by defining an analog to the Ackermann function of page 906 :  [1][n_] = 2n;  [s_][n_] := Nest[  [s - 1], 1, n]  [2][n] is then 2 n ,  [3] is iterated power, and so on. Given this one can now form the "diagonal" function  [ ω ][n_]:=  [n][n] and this has a higher growth rate than any of the  [s][n] with finite s .

If one looks only at the rightmost s columns of the pattern, one sees repetition—but the period of the repetition grows like 2 s . Typical vertical columns have one obvious deviation from randomness: it is twice as probable for the same colors to occur on successive steps than for opposite colors. … Note that if one uses base 6 rather than base 2, then as shown on page 614 powers of 3 still yield a complicated pattern, but all operations are strictly local, and the system corresponds to a cellular automaton with 6 possible colors for each cell and rule {a_, b_, c_}  3 Mod[b, 2] + Floor[c/2] (see page 1093 ).

And in the pictures below one connection is therefore always shown going above the line of nodes, while the other is always shown going below. … Network (a) corresponds to a one-dimensional array, (b) to a two-dimensional array, and (c) to a tree.

At first, the diversity of what one sees is a little overwhelming. … In the very simplest cases, all the cells in the cellular automaton end up just having the same color after one step.

Before the advent of modern computer applications one might have assumed that it did. … Outline of the Principle Across all the vastly different processes that we see in nature and in systems that we construct one might at first think that there could be very little in common.

The relevance of theorems Following traditional mathematical thinking, one might imagine that the best way to be certain about what could possibly happen in some particular system would be to prove a theorem about it. But in my experience, proofs tend to be subject to many of the same kinds of problems as computer experiments: it is easy to end up making implicit assumptions that can be violated by circumstances one cannot foresee.

Random causal networks If one assumes that there are events at random positions in continuous spacetime, then one can construct an effective causal network for them by setting up connections between each event and all events in its future light cone—then deleting connections that are redundant in the sense that they just provide shortcuts to events that could otherwise be reached by following multiple connections.

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. … But for s > 2 , the behavior one sees quickly approaches what is typical for a random mapping in which the network representing the evolution of the 2 m states of the m underlying nodes is itself connected essentially randomly (see page 963 ). (Attempts were made in the 1980s to study phase transitions as a function of s in analogy to ones in percolation and spin glasses.)

So if one could reconstruct sufficiently many complete numbers x from the sequence of Mod[x, 2] values then this would provide a way to factor m (compare the Pollard rho method above). But in practice it is difficult to do this, because without knowing the factors of m one cannot even readily tell whether a given x is a quadratic residue modulo m . … But with m = p q , one has to factor m and find p and q in order to carry out similar tests.

But in an actual physical system one does not expect to be able to find values of amplitudes directly. … Given n spins one can imagine using their 2 n possible configurations to represent each element of Range[m] . But now if one sets up a superposition of all these configurations, one can compute Mod[a # , m]& , then essentially use Fourier to find periodicities—all with a polynomial number of quantum gates.