. • 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.

And from my discussion of intrinsic randomness generation it should come as no surprise that even a completely deterministic rule for the evolution of spins can make the system visit possible states in an effectively random way. … But among all 2 512 9-neighbor rules, there are undoubtedly examples that show effectively random behavior. … And what one sees at least roughly is that right around the phase transition there are patches of black and white of all sizes, forming an approximately nested random pattern.

The encoded version of a sufficiently random sequence grows like n (with the specific encoding used in the text, the length is about 2n ). … With completely random input, the probability that the length b subsequence which begins at element n is a repeat of a previous subsequence is roughly 1 - (1 - 2 -b ) n - 1 .

Indeed, as we saw on page 141 , taking square roots can for example generate seemingly random digit sequences.

In all examples found so far the densest packings can always be repetitive; most can also be highly symmetrical—though in high dimensions random lattices often do not yield much worse results.

But in other cases there are needle-like forms, tree-like or dendritic forms, as well as rounded forms, and forms that seem in many respects random.

As a very simple idealization of biological evolution, one can consider a sequence of cellular automaton programs in which each successive program is obtained from the previous one by a random mutation that adds or modifies a single element.

And in fact in every single case I have in the end reverted either to exhaustive or to purely random searches, with no attempt at iterative improvement.

But what I think is much more likely is that these patterns are instead generated by rules that are in effect chosen at random from among a collection of the simplest possibilities.

Thus, for example, in the early part of this chapter I will discuss the so-called Second Law of Thermodynamics or Principle of Entropy Increase: the observation that many physical systems tend to become irreversibly more random as time progresses.