In the past such an approach would not have seemed sensible, for it was normally assumed that programs small enough to make it work would only ever be able to do rather trivial computations. … The input to the Turing machine is the base 2 digit sequence for the number.

way to get such an answer in a number of steps that increases not exponentially but only like a power.

And in fact I expect that in the end the only way we would unquestionably view a system as being an example of life is if we found that it shared many specific details with life on Earth—probably down, say, to being made of gelatinous materials and having components analogous to proteins, enzymes, cell membranes and so on—and perhaps even down to being based on specific chemical substances like water, sugars, ATP and DNA.

Certainly if the pathways could somehow be seen to support only simple computations then this would be a reasonable conclusion.

Particular conditions amounting to quantization were then imposed on matrices of transitions between these, and the idea was introduced that only certain kinds of amplitude combinations could ever be observed. … But by the 1970s the dozen or so standard processes discussed in QED had been calculated to order α 2 —and by the mid-1980s the anomalous magnetic moment of the electron had been calculated to order α 4 , and nearly one part in a trillion (see note below ). … As mentioned on page 1044 , ordinary quantum field theory in effect deals only with point particles.

So, for example, the smallest solution to x 2  61 y 2 +1 is x  1766319049 , y  226153980 , while the smallest solution to x 3 +y 3  z 3 +2 is x  1214928 , y  3480205 , z  3528875 . Integer equations such as a x + b y + c z  d that have only linear dependence on any variable were largely understood even in antiquity. Quadratic equations in two variables such as x 2  a y 2 + b were understood by the 1800s.

There is again incompleteness, but now there is much more of it, for even statements as simple as x+y  y+x and x+0  x cannot be proved true or false from the axioms. … For it yields only those theorems that hold abstractly for any group.

But now the main way this has been done is by progressively adding axioms so as to get closer to having a system that is complete—with only a rather vague notion of just what underlying objects one is really expecting to describe.

A branch in the resulting tree continues only if it corresponds to a configuration of cell colors whose evolution is consistent with the specified column of colors. … In class 2 examples like rule 10 many intermediate configurations are possible. … No doubt in many cases the number of nodes that have to be visited eventually increases like 2 t , but many branches usually die off quickly, greatly reducing the typical effort required in practice.

Encoding only differences between successive samples leads to perhaps a factor of 2 compression.