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. … And the only possible conclusion from this is that f[i, n] cannot in fact be implemented as a program that always halts—thus demonstrating that the computable real numbers cannot explicitly be enumerated.

(Note however that this is possible in Henkin versions of higher-order logic that allow only limited function domains.)

Only with the advent of computer graphics in the 1970s, however, does the idea appear to have arisen of varying angles to get different forms.

But only very special kinds of systems are in fact ergodic, and even in such systems, the time necessary to visit a significant fraction of all possible states is astronomically long.

This notion was supported by the fact that certain modifications to these operations were found to allow only the exact same set of functions. … Such doubts will in the end only be put to rest by the explicit construction of a discrete fundamental theory along the lines I discuss in Chapter 9 .

But while explicit coordinates and lengths are not usually discussed, it is still imagined that one knows more information than in the networks I consider: not only how vertices are connected by edges, but also how edges are arranged around faces, faces around volumes, and so on. And while in 2D and 3D it is possible to set up such an approximation to any manifold in this way, it turns out that at least in 5D and above it is not. … In fact, the only features of manifolds that ultimately seem relevant are ones that in appropriate limits are determined just from the connectivity of networks.

But by the mid-1990s I had built up a whole intellectual structure that was capable of much more, and that in fact provided the foundations for what could only be considered a fundamentally new kind of science.

And thus for example the first picture below shows that it can take t 2 steps for a Turing machine that updates just one cell at each step to build up the same pattern as a one-dimensional cellular automaton builds up in t steps by updating every cell in parallel. … But what if one asks only about some limited feature of the output—say whether some particular string appears after t steps of evolution of the multiway system? … But the celebrated P=NP question in computational complexity theory asks whether in general there is some To emulate t steps in the evolution of the cellular automaton takes the Turing machine 2t 2 + 5t - 6 steps.

At each level there are many problems known that are complete at that level in the sense that all other problems at that level can be translated to instances of that problem using only computations at a lower level.

But with n variables a DNF-type canonical form can be of size 2 n —and can take up to at least 2 n proof steps to reach. And indeed if logic proofs could in general be done in a number of steps that increases only like a polynomial in n this would mean that the NP-complete problem of satisfiability could also be solved in this number of steps, which seems very unlikely (see page 768 ).