But all this actually does is to force there to be only two objects analogous to True and False .)

And this made informal definitions of complexity often include all sorts of detailed features of life (see page 1178 ). … In general it is possible to imagine setting up all sorts of definitions for quantities that one chooses to call complexity.

Even in antiquity it was nevertheless recognized that all sorts of aspects of language are purely matters of convention, so that shared conventions are necessary for verbal communication to be possible. … In the late 1600s Gottfried Leibniz nevertheless suggested that perhaps a universal language—modelled on mathematics—could be created that would represent all truths in an objective way accessible to any mind (compare page 1149 ).

In the 1700s and 1800s all sorts of celestial mechanics was done on the basis of this—with occasional observational anomalies being resolved for example by the discovery of new planets. … Meanwhile, there continued to be ever more accurate experimental tests of general relativity in the solar system—and at least in the weak gravitational fields available there (with metrics differing from the identity by at most one part in 10 6 ), all have worked out to around the 10 -3 level.

The pictures below show as black squares all the quadratic residues for each successive m going down the page (the ordinary squares 1, 4, 9, 16, ... show up as vertical black stripes).

Note that even though one may only want to find a single digit in m t , I know of no way to do this without essentially computing all the other digits in m t as well.

But even though they seemed to capture or better actual human behavior, the programs considered in all these cases typically just used standard statistical or Markov model methods, or matching of specific sequences—making them far too weak to make predictions about the kinds of complex behavior shown in this book.

[Spectra of] random block sequences Analytical forms for all but the last spectrum are: 1 , u 2 /(1 + 8u 2 ) , 1/(1 + 8 u 2 ) , u 2 , (1 - 4u 2 ) 2 /(1 - 5u 2 + 8u 4 ) , u 2 /(1 - 5u 2 + 8u 4 ) , u 2 + 1/36 DiracDelta[ ω - 1/3] , where u = Cos[ π ω ] , and ω runs from 0 to 1/2 in each plot.

P completeness If one allows arbitrary initial conditions in a cellular automaton with nearest-neighbor rules, then to compute the color of a particular cell after t steps in general requires specifying as input the colors of all 2t + 1 initial cells up to distance t away (see page 960 ).

In the limit, such sequences contain with equal frequency all possible blocks of any given length, but as shown on page 597 , they exhibit other obvious deviations from randomness.