Note that one element of the rule can be considered as specifying that the Turing machine should "halt" with the head staying in the same location and same state.

But after searching through perhaps 50,000 rules, one finally comes across a rule of the kind shown below—in which the compressed pattern exhibits very much the same kind of apparent randomness that we saw in cellular automata like rule 30.

Yet if life had arisen one might expect it to have become widespread, since at least on Earth it has managed to spread to many extremes of temperature, pressure and chemical composition. … But thus far it has not been possible to see—say in planetary atmospheres—whether there are for example molecules similar to ones characteristically found in life on Earth.

And particularly using the methods of this book one will be able to use progressively smaller physical components as elements of computers. … In the past one might have assumed that these changes would somehow show fundamental evidence of representing sophisticated human thinking.

One might imagine that it should be possible to set up a function f[i, n] which if given successive integers i would give the n th base 2 digit in every possible real number. … Analogously, one might imagine that it should be possible to have a function f[i, n] which enumerates all possible programs that always halt, and specifies a digit in their output when given input n .

And it implies that one needs a criterion more sophisticated than immediate predictability to assess a scientific theory—since when computational irreducibility is present this will inevitably be limited. … It is often assumed that one cannot learn much about the world just by studying purely formal systems—and that one has to rely on empirical input.

In formal language theory, questions about regular languages are always decidable, but ones about context-free languages (see page 1103 ) are already often not. … It is also undecidable whether one axiom system is equivalent to another—even for basic logic (see page 1170 ). … It is also for example undecidable whether a given program is the shortest one that produces particular output (see page 1067 ).

Around 330 BC Aristotle mentioned that instead randomness might just be associated with coincidences outside whatever system one is looking at, while around 300 BC Epicurus suggested that there might be randomness continually injected into the motion of all atoms. … One case where there was occasional discussion of origins of randomness from at least the early 1900s was fluid turbulence (see page 997 ). … Traditional mathematical models of natural systems are often expressed in terms of probabilities, but do not normally involve anything one can explicitly consider as randomness.

But the fact that the form of flow should depend only on Reynolds number means that in the pictures in the main text for example it is not necessary to specify absolute sizes or speeds: one need only know the product U L that appears in the Reynolds number. In practice, moving one's finger slowly through water gives a Reynolds number of about 100 (so that a regular array of dimples corresponding to eddies are visible behind one's finger), walking in air about 10,000, a boat in the millions, and a large airplane in the billions.

Even if one assumes that spacetime is in a sense ultimately continuous one can imagine investigating quantum gravity by doing some kind of discrete approximation. … If one computes the product of Exp[  (j 1 + j 2 - j 3 )] for all triangles, then it turns out for example that this quantity is extremized exactly when the whole surface is flat. In 3D one imagines breaking space into tetrahedra whose edge lengths correspond to discrete quantum spin values.