In different situations the reasons for using such probabilistic models have been somewhat different, but before the discoveries in this book one of the key points was that it seemed inconceivable that there could be deterministic models that would reproduce the kinds of complexity and apparent randomness that were so often seen in practice. If one has a deterministic model then it is at least in principle quite straightforward to find out whether the model is correct: for all one has to do is to compare whatever specific behavior the model predicts with behavior that one observes. … As one simple example, consider a model in which all possible sequences of black and white squares are supposed to occur with equal probability.

In the center of the cellular automaton is then a cell whose possible colors correspond to possible points in the program for the register machine. … As one example the bottom picture shows how a cellular automaton can be set up to perform repeated multiplication by 3 of numbers in base 2. And the only real difficulty in this case is that carries generated in the process of multiplication may need to be propagated from one end of the number to the other.

Discrete packings The pictures below show a discrete analog of circle packing in which one arranges as many circles as possible with a given diameter on a grid. … And in fact in general finding such packings is an NP-complete problem: it is equivalent to the problem of finding the maximum clique (completely connected set) in the graph whose vertices are joined whenever they correspond to grid points on which non-overlapping circles could be centered. … But what happens if one generalizes to allow circles of different sizes is not clear.

The fixed points of this procedure are the perfect numbers (see above ). … But if one starts, for example, with the number 276, then the picture below shows the number of base 10 digits in the value obtained at each step.

And one may wonder whether this process will go on forever, or whether at some point it will come to an end, and one will reach a final ultimate model for the universe. … For it has seemed that whenever one tries to get to another level of accuracy, one encounters more complex phenomena. … But one of the crucial points discovered in this book is that more complex phenomena do not always require more complex models.

If one looks not just at specific sequences, but instead at all 2 n possible sequences of length n , one can ask how many cellular automaton rules (say with k = 2 , r = 2 ) one has to go through in order to generate every one of these. … Since some different rules generate the same sequences (see page 956 ) one needs to go through somewhat more than 2 n rules to get every sequence of length n . … (Note that the sequence is the first one that cannot be generated by any of the 256 elementary cellular automata; the first sequence that cannot be generated by any k = 2 , r = 2 cellular automata is probably of length 26.)

And in 1963 Alan Robinson suggested the idea of resolution theorem proving, in which one constructs ¬ theorem ∨ axioms , then typically writes this in conjunctive normal form and repeatedly applies rules like ( ¬ p ∨ q) ∧ (p ∨ q)  q to try to reduce it to False , thereby proving given axioms that theorem is True . … Typical of this effort was the Otter system started in the mid-1980s, which uses the resolution method, together with a variety of ad hoc strategies that are mostly versions of the general ones for multiway systems in the previous note. … In the late 1990s, however, I decided to try the latest systems and was surprised to find that some of them could routinely produce proofs hundreds of steps long with little or no guidance.

It is thus important to read these notes in parallel with the sections of the main text to which they refer, since some necessary points may be made only in the main text.

Nevertheless, from the representation for PrimeQ in the note above it has been shown that the positive values of a particular polynomial with 26 variables, 891 terms and total degree 97 are exactly the primes. (Polynomials with 42 variables and degree 5, and 10 variables and degree 10 45 , are also known to work, while it is known that one with 2 variables cannot.) … Note that one can imagine, say, emulating the evolution of a cellular automaton by having the t th positive value of a polynomial represent the t th step of evolution.

Parameter space sets Points in the space of parameters can conveniently be labelled by a complex number c , where the imaginary direction is taken to increase to the right. … The rest of the boundary consists of a sequence of algebraic curves, with almost imperceptible changes in slope in between; the first corresponds to {0, 0, 0, 1, 0, 1, 0, 1, …} , while subsequent ones correspond to {0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, …} , {0, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, …} , etc. … In practice, however, it is essential to prune the tree of points at each stage.