The Beginning of Infinity: Explanations That Transform the World (32 page)

All undecidable statements are, directly or indirectly, about infinite sets. To the opponents of infinity in mathematics, this is due to the meaninglessness of such statements. But to me it is a powerful argument – like Hofstadter’s 641 argument – that abstractions exist objectively. For it means that the truth value of an undecidable statement is certainly not just a convenient way of describing the behaviour of some physical object like a computer or a collection of dominoes.

Interestingly, very few questions are
known
to be undecidable, even though most are – and I shall return to that point. But there are many unsolved mathematical conjectures, and some of those may well be undecidable. Take, for instance, the ‘prime-pairs conjecture’. A prime pair is a pair of prime numbers that differ by 2 – such as 5 and 7. The conjecture is that there is no largest prime pair: there are infinitely many of them. Suppose for the sake of argument that that is undecidable – using
our
physics. Under many other laws of physics it is decidable. The laws of Infinity Hotel are an example. Again, the details of how the management would settle the prime-pairs issue are not essential to my argument, but I present them here for the benefit of mathematically minded readers. The management would announce:

At the end of five minutes, the management would know the truth of the prime-pairs conjecture.

So, there is nothing
mathematically
special about the undecidable questions, the non-computable functions, the unprovable propositions. They are distinguished by physics only. Different physical laws would make different things infinite, different things computable, different truths – both mathematical and scientific – knowable. It is only the laws of physics that determine which abstract entities and relationships are modelled by physical objects such as mathematicians’ brains, computers and sheets of paper.

Some mathematicians wondered, at the time of Hilbert’s challenge, whether finiteness was really an essential feature of a proof. (They meant mathematically essential.) After all, infinity makes sense mathematically, so why not infinite proofs? Hilbert, though he was a great defender of Cantor’s theory, ridiculed the idea. Both he and his critics were thereby making the same mistake as Zeno: they were all assuming that some class of abstract entities can
prove
things, and that mathematical reasoning could determine what that class is.

But if the laws of physics were in fact different from what we currently think they are, then so might be the set of mathematical truths that we would then be able to prove, and so might the operations that would be available to prove them with. The laws of physics as we know them happen to afford a privileged status to such operations as
not
,
and
and
or
, acting on individual bits of information (binary digits, or logical true/false values). That is why those operations seem natural, elementary and finite to us – and why bits do. If the laws of physics were like, say, those of Infinity Hotel, then there would be additional privileged operations, acting on infinite sets of bits. With some other laws of physics, the operations
not
,
and
and
or
would be non-computable, while some of our non-computable functions would seem natural, elementary and finite.

That brings me to another distinction that depends on the laws of physics:
simple
versus
complex
. Brains are physical objects. Thoughts are computations, of the types permitted under the laws of physics. Some explanations can be grasped easily and quickly – like ‘If Socrates was a man and Plato was a man then they were both men.’ This is easy because it can be stated in a short sentence and relies on the properties
of an elementary operation (namely
and
). Other explanations are inherently hard to grasp, because their shortest form is still long and depends on many such operations. But whether the form of an explanation is long or short, and whether it requires few or many elementary operations, depends entirely on the laws of physics under which it is being stated and understood.

Quantum
computation, which is currently believed to be the fully universal form of computation, happens to have exactly the same set of computable functions as Turing’s classical computation. But quantum computation drives a coach and horses through the classical notion of a ‘simple’ or ‘elementary’ operation. It makes some intuitively very complex things simple. Moreover, the elementary informationstoring entity in quantum computation, the ‘qubit’ (quantum bit) is quite hard to explain in non-quantum terminology. Meanwhile the
bit
is a fairly complicated object from the perspective of quantum physics.

Some people object that quantum computation therefore isn’t ‘real’ computation: it is just physics, just engineering. To them, those logical possibilities about exotic laws of physics enabling exotic forms of computation do not address the issue of what a proof ‘really’ is. Their objection would go something like this: admittedly, under suitable laws of physics we would be able to compute non-Turing-computable functions, but that would not be
computation
. We would be able to establish the truth or falsity of Turing-undecidable propositions, but that ‘establishing’ would not be
proving
, because then our knowledge of whether the proposition was true or false would for ever depend on our knowledge of what the laws of physics are. If we discovered one day that the real laws of physics were different, we might have to change our minds about the proof too, and its conclusion. And so it would not be a real proof: real proof is independent of physics.

Here is that same misconception again (as well as some authority-seeking justificationism). Our
knowledge
of whether a proposition is true or false
always
depends on knowledge about how physical objects behave. If we changed our minds about what a computer, or a brain, has been doing – for instance, if we decided that our own memory was faulty about which steps we had checked in a proof – then we would be forced to change our opinion about whether we had proved
something or not. It would be no different if we changed our minds about what the laws of physics made the computer do.

Whether a mathematical proposition is true or not is indeed independent of physics. But the
proof
of such a proposition is a matter of physics only. There is no such thing as abstractly proving something, just as there is no such thing as abstractly knowing something. Mathematical truth is absolutely necessary and transcendent, but all knowledge is generated by physical processes, and its scope and limitations are conditioned by the laws of nature. One can define a class of abstract entities and call them ‘proofs’ (or computations), just as one can define abstract entities and call them triangles and have them obey Euclidean geometry. But you cannot infer anything from that theory of ‘triangles’ about what angle you will turn through if you walk around a closed path consisting of three straight lines. Nor can those ‘proofs’ do the job of verifying mathematical statements. A mathematical ‘theory of proofs’ has no bearing on which truths can or cannot be proved in reality, or be known in reality; and similarly a theory of abstract ‘computation’ has no bearing on what can or cannot be computed in reality.

So, a computation or a proof is a physical process in which objects such as computers or brains physically model or instantiate abstract entities like numbers or equations, and mimic their properties. It is our window on the abstract. It works because we use such entities only in situations where we have good explanations saying that the relevant physical variables in those objects do indeed instantiate those abstract properties.

Consequently, the reliability of our knowledge of mathematics remains for ever subsidiary to that of our knowledge of physical reality. Every mathematical proof depends absolutely for its validity on our being right about the rules that govern the behaviour of some physical objects, like computers, or ink and paper, or brains. So, contrary to what Hilbert thought, and contrary to what most mathematicians since antiquity have believed and believe to this day, proof theory can never be made into a branch of mathematics. Proof theory is a science: specifically, it is computer science.

The whole motivation for seeking a perfectly secure foundation for mathematics was mistaken. It was a form of justificationism. Mathematics
is characterized by its use of proofs in the same way that science is characterized by its use of experimental testing; in neither case is that the object of the exercise. The object of mathematics is to understand – to
explain
– abstract entities. Proof is primarily a means of ruling out false explanations; and sometimes it also provides mathematical truths that need to be explained. But, like all fields in which progress is possible, mathematics seeks not random truths but good explanations.

Three closely related ways in which the laws of physics seem finetuned are: they are all expressible in terms of a single, finite set of elementary operations; they share a single uniform distinction between finite and infinite operations; and their predictions can all be computed by a single physical object, a universal classical computer (though to simulate physics
efficiently
one would in general need a quantum computer). It is because the laws of physics support computational universality that human brains can predict and explain the behaviour of very un-human objects like quasars. And it is because of that same universality that mathematicians like Hilbert can build up an intuition of proof, and mistakenly think that it is independent of physics. But it is not independent of physics: it is merely universal
in
the physics that governs our world. If the physics of quasars were like the physics of Infinity Hotel, and depended on the functions we call non-computable, then we could not make predictions about them (unless we could build computers out of quasars or other objects relying on the relevant laws). With laws of physics slightly more exotic than that, we would not be able to explain anything – and hence could not exist.

So there is something special –
infinitely
special, it seems – about the laws of physics as we actually find them, something exceptionally computation-friendly, prediction-friendly and explanation-friendly. The physicist Eugene Wigner called this ‘the unreasonable effectiveness of mathematics in the natural sciences’. For the reasons I have given, anthropic arguments alone cannot explain it. Something else will.

This problem seems to attract bad explanations. Just as religious people tend to see Providence in the unreasonable effectiveness of mathematics in science, and some evolutionists see the signature of evolution, and some cosmologists see anthropic selection effects, so some computer scientists and programmers see a great computer in
the sky. For instance, one version of that idea is that the whole of what we usually think of as reality is merely virtual reality: a program running on a gigantic computer – a Great Simulator. On the face of it, this might seem a promising approach to explaining the connections between physics and computation: perhaps the reason the laws of physics are expressible in terms of computer programs is that they are in fact computer programs. Perhaps the existence of computational universality in our world is a special case of the ability of computers (in this case the Great Simulator) to emulate other computers – and so on.

But that explanation is a chimera. An infinite regress. For it entails giving up on explanation in science. It is in the very nature of computational universality that, if we and our world were composed of software, we would have no means of understanding the real physics – the physics underlying the hardware of the Great Simulator.

A different way of putting computation at the heart of physics, and to resolve the ambiguities of anthropic reasoning, is to imagine that
all possible computer programs
are running. What we think of as reality is just virtual reality generated by one or more of those programs. Then we define ‘common’ and ‘uncommon’ in terms of an average over all those programs, counting programs in order of their lengths (how many elementary operations each contains). But again that assumes that there is a preferred notion of what an ‘elementary operation’ is. Since the length and complexity of a program are entirely dependent on the laws of physics, this theory again requires an external world in which those computers run – a world that would be unknowable to us.

Both those approaches fail because they attempt to reverse the direction of the real explanatory connection between physics and computation. They seem plausible only because they rely on that standard mistake of Zeno’s, applied to computation: the misconception that the set of classically computable functions has an a-priori privileged status within mathematics. But it does not. The only thing that privileges that set of operations is that it is instantiated in the laws of physics. The whole point of universality is lost if one conceives of computation as being somehow prior to the physical world, generating its laws. Computational universality is all about computers
inside
our physical
world being related to each other under the universal laws of physics to which we (thereby) have access.