Numbers of [cellular automaton] rules Allowing k possible colors for each cell and considering r neighbors on each side, there are k k 2r + 1 possible cellular automaton rules in all, of which k 1/2 k r + 1 (1 + k r ) are symmetric, and k 1 + (k - 1)(2r + 1) are totalistic. … For k = 2 , r = 2 there are 4,294,967,296 rules in all, of which 64 are totalistic. … Note that for k > 2 , a particular rule will in general be totalistic only for a specific assignment of values to colors.

Hashing Given data in the form of sequences of numbers between 0 and k - 1 , a very simple hashing scheme is just to compute FromDigits[Take[list, n], k] . … Out of the many hundreds of times that I have used hashing in practice, I recall only a couple of cases where schemes like the one just described were not adequate, and in these cases the data always turned out to have quite dramatic regularities. … In the past decade, hashing has become widely used not only for searching but also for authentication.

And if the output from a computation can be of size 2 n then this will normally take at least 2 n steps to generate. … Diagonalization arguments analogous to those on pages 1128 and 1162 show that in principle there must exist functions that can be evaluated only by computations that exceed any given bound. … For example, with deterministic finite automata (see page 957 ), there are sequences that can be recognized, but only by having exponentially many states.

In the specific case a = 4 , however, it turns out that by allowing more sophisticated mathematical functions one can get a complete formula: the result after any number of steps t can be written in any of the forms Sin[2 t ArcSin[ √ x ]] 2 (1 - Cos[2 t ArcCos[1 - 2 x]])/2 (1 - ChebyshevT[2 t , 1 - 2x])/2 where these follow from functional relations such as Sin[2x] 2  4 Sin[x] 2 (1 - Sin[x] 2 ) ChebyshevT[m n, x]  ChebyshevT[m, ChebyshevT[n, x]] For a = 2 it also turns out that there is a complete formula: (1 - (1 - 2 x) 2 t )/2 And the same is true for a = -2 : 1/2 - Cos[(1/3) ( π - (-2) t ( π - 3 ArcCos[1/2 - x]))] In all these examples t enters essentially only in a t . … When a = 2 it is Exp[x] and when a = -2 it is 2 Cos[(1/3) ( π - √ 3 x)] . … (It has long been known that only elliptic functions such as JacobiSN satisfy polynomial addition formulas—but there is no immediate analog of this for replication formulas.)

Most use the same basic scheme: to look for signals that show a narrow band of frequencies—say only 1 Hz wide—perhaps changing in time. … The best current experiments could successfully detect radio emission at the level now produced on Earth only from about 10 light years away—or from about the nearest 10 stars. … But although there are now practical constraints associated with the fact that on Earth only a few frequency regions have been left clear for radio astronomy I consider this to be a remarkable example of reliance on details of human intellectual development.

And indeed, for the shift map what we have seen is that randomness will occur only when the initial conditions that are given happen to be a number whose digit sequence is random.

For Turing machines with two or three possible states, only repetitive and nested behavior normally seem to occur.

So as a consequence, what I do in the remainder of this section is to track only the piece that includes the first node shown in pictures such as those Networks from previous pictures laid out in a uniform way.

Note that the initial conditions consist of a network that contains only a single node.

The pictures on the next page show more examples of class 1 and 2 cellular automata. … But at least for these class 1 and 2 examples, the progression of networks always continues to have a fairly simple form. … On subsequent steps, rule 255 allows only sequences containing just black cells, while rule 4 allows sequences that contain both black and white cells, but requires that every black cell be surrounded by white cells.