One can also allow each node to have a neighborhood that corresponds to any of a set of templates. For templates involving nodes out to distance one, there are 13 minimal sets in the sense of page 941 , of which only 6 contain just one template, 6 contain two and 1 contains three. If one does allow dangling connections to be joined within a single template, the results are similar to those discussed so far.

When one says that a network is planar what one means is that it can be laid out in ordinary 2D space without any lines crossing. … Nevertheless, if one considers minors a finite list does suffice—though for example on a torus it is known that at least 800 (and perhaps vastly more) are needed. (There is in fact a general theorem established since the 1980s that absolutely any list of networks—say for example ones that cannot be laid on a given surface—must actually in effect always all be reducible to some finite list of minors.)

One can also consider whole classes of systems in which rules as well as initial conditions can be chosen. And then one can say for example that as a class of systems cellular automata are universal, but neighbor-independent substitution systems are not.

Trapezoidal primes If one lays out n objects in an a × b rectangular array, then n is prime if either a or b must be 1 . Following the Pythagorean idea of figurate numbers one can instead consider laying out objects in an array of b rows, containing successively a , a - 1 , ... objects.

In addition, instead of modelling the displacement of atoms, one can try to model directly the presence or absence of atoms at particular positions. And then one can start from a repetitive array of cells, with a perturbation to represent the beginning of the crack.

Basic theory [of cryptography] As was recognized in the 1920s the only way to make a completely secure cryptographic system is to use a so-called one-time pad and to have a key that is as long as the message, and is chosen completely at random separately for each message. As soon as there are a limited number of possible keys then in principle one can always try each of them in turn, looking in each case to see whether they imply an original message that is meaningful in the language in which the message is written. … If one guesses a key it will normally take a time polynomial in n to check whether the key is correct, and thus the problem of cryptanalysis is in the class known in theoretical computer science as NP or non-deterministic polynomial time (see page 1142 ).

And indeed with integer equations, as soon as one has a general equation that is universal, it typically follows that there will be specific instances in which the absence of solutions—or at least of solutions of some particular kind—can never be proved on the basis of the normal axioms of arithmetic. … But the examples that have actually been constructed are quite complicated—like the one on page 786 —with the simplest involving 9 variables and an immense number of terms. … If one just starts looking at sequences of integer equations—as on the next page —then in the very simplest cases it is usually fairly easy to tell whether a particular equation will have any solutions.

Systems like rule 110 shown below have a kind of local coherence in their behavior that reminds one of the operation of traditional engineering systems—or of purposeful human activity. … For although one can see that such systems have a lot going on, one tends to assume that somehow none of it is coherent enough to achieve any definite purpose.

Identifying the 171 patterns [that satisfy 2D constraints] The number of constraints to consider can be reduced by symmetries, by discarding sets of templates that are supersets of ones already known to be satisfiable, and by requiring that each template in the set be compatible with itself or with at least one other in each of the eight immediately adjacent positions.

So to avoid this one can consider systems that are more like circuits in which any element can get data from any other. And given t elements operating in parallel one can consider the class NC studied by Nicholas Pippenger in 1978 of computations that can be done in a number of steps that is at most some power of Log[t] . … There is no way yet known to establish this for certain, but just as with NP and P one can consider showing that a computation is P-complete with respect to transformations in NC.