
Rene Descartes, Discourse on Method (Discours de la methode pour bien conduire sa raison, & chercher la verité dans les sciences)
==========
We’ll start today with a ten-minute talk by Dave Adams on Ch 10. And here’s some background information he has collected for us about Shor’s algorithm.
In Chapter 2, Descartes sets out his four rules of proof.
The first was never to accept anything for true which I did not clearly know to be such; that is to say, carefully to avoid precipitancy and prejudice, and to comprise nothing more in my judgement than what was presented to my mind so clearly and distinctly as to exclude all ground of doubt.
The second, to divide each of the difficulties under examination into as many parts as possible, and as might be necessary for its adequate solution.
The third, to conduct my thoughts in such order that, by commencing with objects the simplest and easiest to know, I might ascend by little and little, and, as it were, step by step, to the knowledge of the more complex; assigning in thought a certain order even to those objects which in their own nature do not stand in a relation of antecedence and sequence.
And the last, in every case to make enumerations so complete, and reviews so general, that I might be assured that nothing was omitted.
==========
Descartes represents a tradition that Deutsch traces back to Aristotle, according to which a proof is a sequence of statements that obey rules of inference. This is the idea that a proof is a type of object. Deutsch argues for a view of proof as a process. Proof-as-process becomes inevitable, and irreducible to proof-as-object, in the context of computations that require quantum computation. Here is the key passage (page 251):
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, 10<sup>500</sup> universes. To make the point more clearly, let the calculation be such that the answer (unlike the result of 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.
Read the rest of this entry »