But in practice methods based, for example, on genetic programming seem to do at best only about as well as all sorts of other methods discussed in this chapter. … So it is then notable that biological evolution has apparently never made predators able to catch their prey by predicting anything that looks to us particularly random; instead strategies tend to be based on tricks that do not require predicting more than at most repetition.

Non-computable [2D] patterns It is known to be possible to set up constraints that will force patterns in which finding the color of a particular cell can require doing something like solving a halting problem—which cannot in general be done by any finite computation.

Directional reversibility [in cellular automata] Even if successive time steps in the evolution of a cellular automaton do not correspond to an injective map, it is still possible to get an injective map by looking at successive lines at some angle in the spacetime evolution of the system.

In general one tends to talk of purpose only when doing so allows one to give a simpler description of some aspect of behavior than just describing the behavior directly. … And so, for example, while the digits of π have a simple description in terms of traditional mathematics, the results in Chapter 4 suggest that outside of this framework they normally do not.

. • Different programs for doing all sorts of different things can be set up. • Any given program can be implemented in many ways. • Programs can behave in complicated and seemingly random ways—particularly when they are not working properly. • Debugging a program can be difficult. • It is often difficult to foresee what a program can do by reading its code. • The lower the level of representation of the code for a program the more difficult it tends to be to understand. • Some computational problems are easy to state but hard to solve. • Programs that simulate natural systems are among the most computationally expensive. • It is possible for people to create large programs—at least in pieces. • It is almost always possible to optimize a program more, but the optimized version may be more difficult to understand. • Shorter programs are sometimes more efficient, but optimizations often require many cases to be treated separately, making programs longer. • If programs are patched too much, they typically stop working at all.

But almost without exception the emphasis was on studying what such functions could in principle do, not on looking at the actual behavior of particular ones. And indeed, despite their simple forms, recursive sequences of the kind I discuss here do not for the most part ever appear to have been studied before—although sequence (c) was mentioned in lectures by John Conway around 1988, and the first 17 terms of sequence (e) were given by Douglas Hofstadter in 1979.

Examples of sequences generated by rules that do not depend only on elements a fixed distance back.

It turns out that they do not.

And indeed when random initial conditions are used, rule 90 does manage to produce random behavior of the kind expected in class 3.

With most rules, systems like cellular automata do not usually exhibit such conservation laws.