Slashdot Mirror
Quantum Test Found For Mathematical Undecidability
KentuckyFC writes "Philosophers have long wondered at the profound link between mathematics and physics, but how deep does this connection go? Pretty deep according to the results of a quantum experiment exploring the nature of mathematical undecidability. Here's how: any logical system must be based on axioms, which are propositions that are defined to be true. A proposition is logically independent from these axioms if it can neither be proved nor disproved from them; mathematicians say it is undecidable. In the experiment, researchers encoded a set of axioms as quantum states. A particular measurement on this system can then be thought of as a proposition which, if undecidable, yields a random result — which is what they found. 'This sheds new light on the (mathematical) origin of quantum randomness in these measurements,' say the researchers (abstract)."
It's a bit hard to explain all this stuff in few words. I could refer you to about half a dozen Wikipedia and Wolfram articles on the subjects and you'd still be in the dark. Instead I'll suggest you read GÃdel, Escher, Bach by Douglas Hofstadter, who tackles many of those subjects in an amusing and educational way.
If he explores all forms and substances Straight homeward to their symbol-essences; He shall not die.
From what I understood, they use qubits to encode facts about finite boolean functions. For example, they can use a number of qubits to encode a situation where f:{0,1}->{0,1} and f(0) = 0. Sure enough, the proposition f(1) = 0 is undecidable from the given information, and they claim that they can measure this fact, which, imho, is really cool.
However, those people who wanted to use qubits to establish consistency results should not hold their breath. For a finite structure, decidability of any statement can be checked by going through a long table. To do anything ineteresting, one would have to use infinitely many qubits, which I do not see happening.
They found a way to physically encode a mathematical "axiom" into quantum states. They set up a particular axiom as a quantum state machine, then measure the system. The measurement is done in such a way that it is equivalent to asking "is X true given this axiom?" where X is any mathematical "proposition". The answer to that question can be "yes", "no", or "not enough information". If the latter is the case, the results from the physical quantum experiment will show a random distribution.
So, if I have a mathematical proposition and I'm not sure if it is supported by a certain axiom, I could actually build the axiom into a quantum state machine and measure it in a way that tests my particular proposition. If the results after multiple runs are distributed randomly, then it means that the axiom can not prove or disprove the proposition.
They most certainly DO sell lobster, but periodically. However, you're right, nobody buys it, because it's disgusting.
I looked at this, an an apparently related PhD thesis (http://eprintweb.org/S/article/quant-ph/0812.0238).. I'm not so sure about the 'deepness' of the connection here. It seems to me the basic rationale is along the lines of: - In math, there are propositions that are undecidable given a set of axioms (Gödel) - A guy named Chatain (Int J Theor Phys, v21, 941) suggested that undecidabilty is due to a kind of information-theoretical incompleteness. Or in analogy to basic math: You can't solve a problem with more variables than given relationships. - Now, they went from this, to Quantum Physics, which says that an indeterminate property of a physical system will have a random value, experimentally. (Checking up on this, it seems this result has already been reached before though: Calude and Stay, Int J Theor Phys v46, p2013). So.. seems to me they're saying "Yes, nature follows logic". Which is what Science always assumed. (and it'd be a bitch if it didn't) Maybe I'm missing some very subtle points here. But it all seems rather trivial. A stating of the fact "that which is logically indeterminable is indeterminate".
Actually, that is exactly what they are testing. They want to see what happens when they don't ask the right question.
They took a question that is asked "incorrectly", meaning there is ambiguity in either the proposition or the axioms used. Then they used the concept of quantum states to model the correct answers to this system. Since there is ambiguity, they know there will be more than one answer. What they wanted to know is what the cloud of answers looked like, either random or ordered in a fashion.
They expected to see something similar to what we see in quantum mechanics when we are not precise (i.e. not precisely measuring any particular attribute of the quanta), which is a cloud of randomly distributed results. And that is exactly what they saw.
Pretty cool to me!
There was an equation, which had a term with a square root. As a result of the way math works, if you have a positive square root, you also have a negative one (that's the level of existence I was referring to). That negative square root in the equation told us there should be anti-particles. The simple fact that the equation had to account for the case of the negative square root led us to look for these things, and, they were there is kinda of impressive when you think about it. The universe didn't have to oblige us and put a particle in there, but, nonetheless, it's there.
But, I'm not -- not even a little. I'm saying that our math was built up around our understanding of the physics (as well as some purely mathematical endeavors), but that the math can actually predict the physics, and that the physics seems to always follow the rules that the math adheres to is quite startling. It should model all the known phenomenon, but predicting the new ones is more than you'd think.
That was the gist of it when I linked to this -- that the math is much more intimately linked with the physics than you'd expect.
Meaning, some really big brains in math and physics have been awed by the fact that the math isn't independent of the physics. And reality doesn't ever seem to violate the math.
Cheers
Lost at C:>. Found at C.
No.
This is a method to determine whether or statements are part of a system, not whether they are true or false within the system.
So, it can tell you whether or not there is an answer, but not what the answer is.
Furthermore, it can only truly prove that something is not a member of the system, because then you get different answers when you query the system. But if you keep getting the same answers, well, that could just be coincidence. Hence, you can be fairly certain, but it is not the same thing as a proof.
When things get complex, multiply by the complex conjugate.
First, let me say this is extremely subtle stuff. I won't claim to understand it with even passing familiarity. But the summary and the article (which is a summary of a research paper) give enough clues to provide an educated guess.
Part of quantum mechanics involves the idea that some kinds of measurements are incompatible. For example, the famous Heisenberg principle says you can't make a measurement on a particle's position and velocity and get accurate measurements for each. If you make a measurement on position you'll get a result, and a physicist would then say that the particle is in a quantum state that has a well-defined position operator (actually he'd say that the particle is in an eigenstate of the position operator). You could make the measurement a second time, and you'd get the same position. Ditto for the third, fourth, etc time as well.
If you now go and try and measure velocity (momentum actually), you will also get a result. A physicist would write that particle is now in a quantum state with a well-defined momentum operator. Here's the catch: if you then go back and try to measure the particle's position again, you'll get a random result. It isn't possible to get a quantum state that has both position and momentum operators being well-defined.
Some kinds of operators are compatible, though. For those with some quantum mechanics knowledge, it would be possible to simultaneously measure the total magnetic spin of a particle (S^2) and the spin component along one axis (Sz). The mathies would talk about Hilbert spaces and diagonalizable matrices, but for our purposes we'll just say that the quantum state has several well defined operators.
So...my (limited) understanding of the paper is that the authors propose encoding a set of mathematical axiom by setting a particle into a quantum eigenstate that admits multiple well-defined operators, with each separate operator corresponding to a particular mathematical axiom.
If a particular mathematical proposition is compatible with the given set of axioms, it will then be associated with a well-defined quantum operator of the particle. Making a measurement would then give the same answer each time (like measuring position over and over). But, if the proposition were undecidable, then the quantum operator would not be well-defined, and the measurement would produce a different (random) result each time.
Actually implementing such a system would be another question entirely but, like so much of quantum mechanics, it does pose interesting thought experiments.
Okay, I'll try.
A formal system is an initial set of statements and a set of rules that can be applied to those statements to create additional statements. The initial statements are axioms. The additional statements are theorems. Standard logic is one such system, and arithmetic is another.
A statement is decidable if it can be proven true or false; that is, either the statement can be proven true or the negation of the statement can be proven true. A formal system is complete if and only if all statements written in the language of the formal system are decidable. Arithmetic is not complete (see Godel), nor can enough axioms be added to make it complete. Some formal systems can be made complete by adding enough axioms.
This paper states that, given a system that could be made complete, the axioms can be encoded in quantum states, and that repeated measurements corresponding to a statement will either give either an unvarying result or a random one. If the result is unvarying, then the statement is decidable, and if the result is random, then the statement is undecidable.
While this is interesting, they mention in the paper that a classical (read: non-quantum) machine could be built to do the same thing. Further, you never actually prove anything, as n identical results could conceivably occur randomly. Finally, this work only applies to systems that can be made complete, so don't hold your breath waiting for the Riemann hypothesis to be solved using this method.
This is not bias. Its called credit. When someone spend years saying credible things you are expected to take his declarations seriously. He can be wrong, but his opinion has to be respected and evaluated with caution
-- dnl