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.