If one knew the fundamental rules for the universe then one way in principle to define the amount of computation associated with a given process would be to find the minimum number of applications of the rules for the universe that are needed to reproduce the process at some level of description.

Continual injection of randomness [in cellular automata] In the main text we discuss what happens when one starts from random initial conditions and then evolves according to a definite cellular automaton rule. As an alternative one can consider starting with very simple initial conditions, such as all cells white, and then at each step randomly changing the color of the center cell.

Evolving to predict [data] If one thinks that biological evolution is infinitely powerful one might imagine that by emulating it one would always be able to find ways to predict any sequence of data.

On an infinitely long interface, protrusions of cells with one color into a domain of the opposite color get progressively smaller, eventually leaving only a certain pattern of cells in the layer immediately on one side of the interface. 90° corners in an otherwise flat interface effectively act like reflective boundary conditions for the layer of cells on top of the interface. … One example is totalistic code 52, which is a direct analog in the 4-neighbor case of the rule illustrated here.

I believe, however, that this is not the case, and that the reason for the impression is just that it is usually so much more difficult even to represent the states of continuous systems that one normally tends to work only with ones that have comparatively simple overall behavior—and are therefore more readily described by formulas. … And if one assumes that this is a general feature then one can formally derive for any a the result 1/2 (1 - g[a t InverseFunction[g] [1 - 2x]]) where g is a function that satisfies the functional equation g[a x]  1 + (a/2) (g[x] 2 - 1) When a = 4 , g[x] is Cosh[Sqrt[2 x]] . … Given the functional equation one can find a power series for g[x] for any a .

Feedback [in visual processing] Most of the lowest levels of visual processing seem to involve only signals going successively from one layer in the eye or brain to the next. But presumably there is at least some feedback to previous layers, yielding in effect iteration of rules like the ones used in the main text.

Density of universal systems One might imagine that it would be possible to make estimates of the overall density of universal systems, perhaps using arguments like those for the density of primes, or for the density of algorithmically random sequences. … If one has shown that various simple rules are universal, then it follows that rules which generalize these must also be universal.

The constraint requires that the arrangement of colors around each cell must match one of the 12 templates shown, and that at least somewhere in the pattern a template containing a pair of stacked black cells must occur.

The basic idea is to have m outputs as well as m inputs—with every one of the 2 m possible sets of inputs mapping to a unique set of outputs. Normally one specifies the first n inputs, taking the others to be fixed, and then looks say at the first output, ignoring all others. One can represent the inside of such a system much like a sorting network from page 1142 —but with s -input s -output gates instead of pair comparisons.

In the 1960s such ideas were increasingly formalized, particularly for execution times on Turing machines, and in 1965 the suggestion was made that one should consider computations feasible if they take times that grow like polynomials in their input size. … A variety of additional classes of computations—notably ones like NC with various kinds of parallelism, ones based on circuits and ones based on algebraic operations—were defined in the 1970s and 1980s, and many detailed results about them were found.