*Excerpt from an essay of David Deutsch*

Turingâ€™s basic insight: Proof is computation, computation is physical, therefore proof is physical

*That it isn't seemed to me like a philosophical absurdity but that was the Mathematicians' Misconception - they believed proof isn't physical*

Just to be clear: Mathematical facts â€“ like Fermatâ€™s last theorem â€“ arenâ€™t physical. That thereâ€™s a difference between truth and provability was the main point of all those 1930s discoveries.

It expresses the idea, acknowledged or not, that somewhere out there, in the world of mathematical abstractions, or in some supernatural world of mathematical intuition, there is the authentic, official, though ineffable (now we know that Hilbert was wrong), definition of proof.

And if some physical process that doesnâ€™t conform to that definition, turns out to allow us to know some new, necessary truth, that process wouldnâ€™t constitute a proof of that truth. Thereâ€™s the misconception.

A few years later, I gave a talk in Oxford, arguing that it makes no sense to regard Turingâ€™s conjecture, in any form, as something one might hope to prove one day from logic, like Fermatâ€™s last theorem. But that it could be proved to be a property of quantum mechanics

It so happens that a quantum computerâ€™s repertoire of integer functions is the same as the Turing machineâ€™s. They differ only in speed.

So some people view this as vindicating the Mathematiciansâ€™ Misconception. But no. First of all, we only know that â€˜they only differ in speedâ€™, from physics, from quantum theory. And second, quantum theory wonâ€™t be the final theory in physics â€“ and even if it is, you canâ€™t prove that either, from mathematical intuition. In reality, we only have physical intuition: never provable, always incomplete and full of errors. The misconception also affects thinking about information. For example, a quantum cryptographic device may perform a classical information-processing task, that is provably impossible classically.

So the misconception makes people say â€˜well, quantum cryptography isnâ€™t an information-processing task; itâ€™s just an engineering task, like building a washing machineâ€™. Why? Just because Turing machines couldnâ€™t perform it!

The question about why mathematics is â€˜unreasonably effective in scienceâ€™, is not that the physical world is actually being computed, on a vast computer â€“ belonging to God. Or to super-normal aliens â€“ Snailiens. Because thereâ€™s no reason, other than the Misconception, why the Snailiensâ€™ computer should itself generate that particular tiny piece of mathematics we call â€˜computableâ€™. Purely mathematical intuition will never reveal anything about proof, or computation, or probability, or information.** If you want to understand any of those fundamentally, you must start with laws of physics.** And in particular with what is currently the most fundamental theory in physics: quantum theory. It wonâ€™t always be the most fundamental. But its replacement will not come from mathematics, logic, or the supernatural.