At least one of Gödel’s intuitions about proof turns out to have been mistaken; fortunately, it happens not to affect the proofs of his theorems. He inherited it intact from the prehistory of Greek mathematics, and it remained unquestioned by every generation of mathematicians until it was proved false in the 1980s by discoveries in the quantum theory of computation. It is the intuition that a proof is a particular type of object, namely a sequence of statements that obey rules of inference. I have already argued that a proof is better regarded not as an object but as a process, a type of computation. But in the classical theory of proof or computation this makes no fundamental difference, for the following reason. If we can go through the process of a proof, we can, with only a moderate amount of extra effort, keep a record of everything relevant that happens during that process. That record, a physical object, will constitute a proof in the sequence-of-statements sense. And conversely, if we have such a record we can read through it, checking that it satisfies the rules of inference, and in the process of doing so we shall have proved the conclusion. In other words, in the classical case, converting between proof processes and proof objects is always a tractable task.
Now consider some mathematical calculation that is intractable on all classical computers, but suppose that a quantum computer can easily perform it using interference between, say, 10500 universes. To make the point more clearly, let the calculation be such that the answer (unlike the result of a factorization) cannot be tractably verified once we have it. The process of programming a quantum computer to perform such a computation, running the program and obtaining a result, constitutes a proof that the mathematical calculation has that particular result. But now there is no way of keeping a record of everything that happened during the proof process, because most of it happened in other universes, and measuring the computational state would alter the interference properties and so invalidate the proof. So creating an old-fashioned proof object would be infeasible; moreover, there is not remotely enough material in the universe as we know it to make such an object, since there would be vastly more steps in the proof than there are atoms in the known universe. This example shows that because of the possibility of quantum computation, the two notions of proof are not equivalent. The intuition of a proof as an object does not capture all the ways in which a mathematical statement may in reality be proved.
Once again, we see the inadequacy of the traditional mathematical method of deriving certainty by trying to strip away every possible source of ambiguity or error from our intuitions until only self-evident truth remains. That is what Gödel had done. That is what Church, Post and especially Turing had done when trying to intuit their universal models for computation. Turing hoped that his abstracted-paper-tape model was so simple, so transparent and well defined, that it would not depend on any assumptions about physics that could conceivably be falsified, and therefore that it could become the basis of an abstract theory of computation that was independent of the underlying physics. ‘He thought,’ as Feynman once put it, ‘that he understood paper.’ But he was mistaken. Real, quantum-mechanical paper is wildly different from the abstract stuff that the Turing machine uses. The Turing machine is entirely classical, and does not allow for the possibility that the paper might have different symbols written on it in different universes, and that those might interfere with one another. Of course, it is impractical to detect interference between different states of a paper tape. But the point is that Turing’s intuition, because it included false assumptions from classical physics, caused him to abstract away some of the computational properties of his hypothetical machine, the very properties he intended to keep. That is why the resulting model of computation was incomplete.
That mathematicians throughout the ages should have made various mistakes about matters of proof and certainty is only natural. The present discussion should lead us to expect that the current view will not last for ever, either. But the confidence with which mathematicians have blundered into these mistakes and their inability to acknowledge even the possibility of error in these matters are, I think, connected with an ancient and widespread confusion between the methods of mathematics and its subject-matter. Let me explain. Unlike the relationships between physical entities, relationships between abstract entities are independent of any contingent facts and of any laws of physics. They are determined absolutely and objectively by the autonomous properties of the abstract entities themselves. Mathematics, the study of these relationships and properties, is therefore the study of absolutely necessary truths. In other words, the truths that mathematics studies are absolutely certain. But that does not mean that our knowledge of those necessary truths is itself certain, nor does it mean that the methods of mathematics confer necessary truth on their conclusions. After all, mathematics also studies falsehoods and paradoxes. And that does not mean that the conclusions of such a study are necessarily false or paradoxical.
Necessary truth is merely the subject-matter of mathematics, not the reward we get for doing mathematics. The objective of mathematics is not, and cannot be, mathematical certainty. It is not even mathematical truth, certain or otherwise. It is, and must be, mathematical explanation.
Why, then, does mathematics work as well as it does? Why does it lead to conclusions which, though not certain, can be accepted and applied unproblematically for millennia at least? Ultimately the reason is that some of our knowledge of the physical world is also that reliable and uncontroversial. And when we understand the physical world sufficiently well, we also understand which physical objects have properties in common with which abstract ones. But in principle the reliability of our knowledge of mathematics remains subsidiary to 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, be they virtual-reality generators, ink and paper, or our own brains.
So mathematical intuition is a species of physical intuition. Physical intuition is a set of rules of thumb, some perhaps inborn, many built up in childhood, about how the physical world behaves. For example, we have intuitions that there are such things as physical objects, and that they have definite attributes such as shape, colour, weight and position in space, some of which exist even when the objects are unobserved. Another is that there is a physical variable — time — with respect to which attributes change, but that nevertheless objects can retain their identity over time. Another is that objects interact, and that this can change some of their attributes. Mathematical intuition concerns the way in which the physical world can display the properties of abstract entities. One such intuition is that of an abstract law, or at least an explanation, that underlies the behaviour of objects. The intuition that space admits closed surfaces that separate an ‘inside’ from an ‘outside’ may be refined into the mathematical intuition of a set, which partitions everything into members and non-members of the set. But further refinement by mathematicians (starting with Russell’s refutation of Frege’s set theory) has shown that this intuition ceases to be accurate when the sets in question contain ‘too many’ members (too large a degree of infinity of members).