The Beginning of Infinity

by David Deutsch

  First: Please check within the next minute whether your room number and the number two above it are both primes.

  Next: If they are, then send a message back through lower-numbered rooms saying that you have found a prime pair. Use the usual method for sending rapid messages (allow one minute for the first step and thereafter each step must be completed in half the time of the previous one). Store a record of this message in the lowest-numbered room that is not already storing a record of a previous such message.

  Next: Check with the room numbered one more than yours. If that guest is not storing such a record and you are, then send a message to room 1 saying that there is a largest prime pair.

  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.

  How do all those drastic limitations on what can be known and what can be achieved by mathematics and by computation, including the existence of undecidable questions in mathematics, square with the maxim that problems are soluble?

  Problems are conflicts between ideas. Most mathematical questions that exist abstractly never appear as the subject of such a conflict: they are never the subject of curiosity, never the focus of conflicting misconceptions about some attribute of the world of abstractions. In short, most of them are uninteresting.

  Moreover, recall that finding proofs is not the purpose of mathematics: it is merely one of the methods of mathematics. The purpose is to understand, and the overall method, as in all fields, is to make conjectures and to criticize them according to how good they are as explanations. One does not understand a mathematical proposition merely by proving it true. This is why there are such things as mathematics lectures rather than just lists of proofs. And, conversely, the lack of a proof does not necessarily prevent a proposition from being understood. On the contrary, the usual order of events is for the mathematician first to understand something about the abstraction in question and then to use that understanding to conjecture how true propositions about the abstraction might be proved, and then to prove them.

  A mathematical theorem can be proved, yet remain for ever uninteresting. And an unproved mathematical conjecture can be fruitful in providing explanations even if it remains unproved for centuries, or even if it is unprovable. One example is the conjecture known in the jargon of computer science as ‘P ≠ NP’. It is, roughly speaking, that there exist classes of mathematical questions whose answers can be verified efficiently once one has them but cannot be computed efficiently in the first place by a universal (classical) computer. (‘Efficient’ computation has a technical definition that roughly approximates what we mean by the phrase in practice.) Almost all researchers in computing theory are sure that the conjecture is true (which is further refutation of the idea that mathematical knowledge consists only of proofs). That is because, although no proof is known, there are fairly good explanations of why we should expect it to be true, and none to the contrary. (And so the same is thought to hold for quantum computers.)

  Moreover, a vast amount of mathematical knowledge that is both useful and interesting has been built on the conjecture. It includes theorems of the form ‘ if the conjecture is true then this interesting consequence follows.’ And there are fewer, but still interesting, theorems about what would follow if it were false.

  A mathematician studying an undecidable question may prove that it is undecidable (and explain why). From the mathematician’s point of view, that is a success. Though it does not answer the mathematical question, it solves the mathematician’s problem. Even working on a mathematical problem without any of those kinds of success is still not the same as failing to create knowledge. Whenever one tries and fails to solve a mathematical problem one has discovered a theorem – and usually also an explanation – about why that approach to solving it does not work.

  Hence, undecidability no more contradicts the maxim that problems are soluble than does the fact that there are truths about the physical world that we shall never know. I expect that one day we shall have the technology to measure the number of grains of sand on Earth exactly, but I doubt that we shall ever know what the exact number was in Archimedes’ time. Indeed, I have already mentioned more drastic limitations on what can be known and achieved. There are the direct limitations imposed by the universal laws of physics – we cannot exceed the speed of light, and so on. Then there are the limitations of epistemology: we cannot create knowledge other than by the fallible method of conjecture and criticism; errors are inevitable, and only errorcorrecting processes can succeed or continue for long. None of this contradicts the maxim, because none of those limitations need ever cause an unresolvable conflict of explanations.

  Hence I conjecture that, in mathematics as well as in science and philosophy, if the question is interesting, then the proble
m is soluble. Fallibilism tells us that we can be mistaken about what is interesting. And so, three corollaries follow from this conjecture. The first is that inherently insoluble problems are inherently uninteresting. The second is that, in the long run, the distinction between what is interesting and what is boring is not a matter of subjective taste but an objective fact. And the third corollary is that the interesting problem of why every problem that is interesting is also soluble is itself soluble. At present we do not know why the laws of physics seem fine-tuned; we do not know why various forms of universality exist (though we do know of many connections between them); we do not know why the world is explicable. But eventually we shall. And when we do, there will be infinitely more left to explain.

  The most important of all limitations on knowledge-creation is that we cannot prophesy: we cannot predict the content of ideas yet to be created, or their effects. This limitation is not only consistent with the unlimited growth of knowledge, it is entailed by it, as I shall explain in the next chapter.

  That problems are soluble does not mean that we already know their solutions, or can generate them to order. That would be akin to creationism. The biologist Peter Medawar described science as ‘the art of the soluble’, but the same applies to all forms of knowledge. All kinds of creative thought involve judgements about what approaches might or might not work. Gaining or losing interest in particular problems or sub-problems is part of the creative process and itself constitutes problem-solving. So whether ‘problems are soluble’ does not depend on whether any given question can be answered, or answered by a particular thinker on a particular day. But if progress ever depended on violating a law of physics, then ‘problems are soluble’ would be false.