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)."
this may or may not be first post, but one thing is for certain: you suck.
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.
Ah, but now you've changed it again. ;-)
Cheers
Lost at C:>. Found at C.
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.
Philosophers have long wondered at the profound link between mathematics and physics, but how deep does this connection go?
What an utterly meaningless bit of drivel. Any philosopher wondering this ought to turn in his license.
"Physics" is (to simplify) the scientific study of what rules the universe operates under. It's entirely possible and reasonable we can determine universal laws without having the faintest idea of *why* they are that way. It's observed truth that might even be totally different in a different part of the universe (we assume it's not, but that's just an assumption).
Mathematics is an abstract game of counting, built up into great complexity. 1 + 1 = 2 will be true in any universe, under any god(s), in any circumstances. And all of mathematics is built up from that. It's universal truth.
We use mathematics to quantify physics, but there is no "connection" between the two, except in the sense that we can count *anything* and say there's a connection. It's like saying, "How deep does the connection go between mathematics and bananas when I observe there are 10 bananas, and I add two more, and then I observe 12 bananas."
Sometimes it's best to just let stupid people be stupid.
I suppose you could think of it as testing "computability." If your proposition is understandable by the quantum system you set up, it will spit out an answer. And you'll always get that answer.
But if it is not understandable by the quantum system you set up, then no operation is performed, and whatever comes out is simply the result of quantum randomness.
When things get complex, multiply by the complex conjugate.
Didn't Rush have a song about this?
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.
Okay, disclaimer: I suck at math. ^_^ That said -- how does this actually prove anything? How do they know that the way they set the system up isn't the reason why its creating random results and another system could be created that has all those axioms in it and doesn't produce a random result? Put another way -- how do they know amongst all the possible configurations that there isn't one?
I've always looked at math as more of a language than a discipline, so in my own way I guess what I'm saying is how do they know they're asking the question right?
#fuckbeta #iamslashdot #dicemustdie
Can someone please explain in layman's terms how this results in a decision, for those of us who aren't quantum mathematicians? I somewhat get the whole "indecision results in a decision" thing but seems to be a hard idea to wrap my brain around so to speak.
They're saying that no one orders lobster at McDonald's -- not because people don't like lobster, but because it's not on the menu. You can't base how the general population feels about lobster by asking McDonald's how many lobsters they sell compared to how many hamburgers.
:\
So instead of looking to see what people feel about lobster, they're asking restaurants how many lobsters they sell in order to determine if lobster is even on the menu. Once that's set in stone, THEN they can start testing the demographics of how many people prefer lobster to what.
At least that's how I interpreted what they're doing...
I am the richest astronaut ever to win the superbowl.
They most certainly DO sell lobster, but periodically. However, you're right, nobody buys it, because it's disgusting.
Does this also mean we could also prove theorems by physical experiment?
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".
instruction book that we wrote to describe physics?
There's the thing that you don't understand. We didn't create mathematics to describe physics, yet mathematics always seems to do the job, and ussually much more simply than you would expect.
How many of us sat through algebra in middle school thinking "I'll never use this". Then sat through calculous in high school thinking "Nobody would ever use this". Then took our first calc based physics course in high school and thought, "No way, this is actually how the universe works?".
As far as we can determine, mathematics is the universal language of the universe, it certainly isn't something that we created. The fact that we are near to describing the infinately complex universe with a handful of equations would seem to indicate that mathematics is a part of the very stucture of the universe.
1 Black Hole + 1 Black Hole != 2 Black Holes
It's precisely the fact that the math isn't independent of the physics that is at issue here That's a very startling proposition
The word "math" refers to a huge collection of symbolic rule sets. These rule sets were not all invented at once by some magical mathematician in the past. They were produced over thousands of years of refinement.
One important point to note here is that many of these refinements were made specifically for the purpose of giving math a higher level of practical value. For example, the number zero, and subsequently the negative numbers, were added by most cultures only after they realized that they could derive a useful model of some aspect of reality by using these numbers.
I don't see why it would be surprising at all that a language which has been refined, over time, to describe reality would wind up describing reality.
I will further suggest that the truths of mathematics that seem intuitively obvious to us seem so only because our brains are structured such that these truths will seem intuitively obvious. What gave our brains this structure? Refinement-after-refinement due to the process of natural selection. So the reality which is being modeled by mathematics happens to be the same reality in which the inventors of mathematics (ie our brains) evolved. Who would have ever guessed that there would be some correspondence here?
I think the surprise only comes about when we forget the true origins of mathematics, and the true origins of the brains that understand mathematics and use it to represent reality.
Can someone please explain in layman's terms how this results in a decision, for those of us who aren't quantum mathematicians? I somewhat get the whole "indecision results in a decision" thing but seems to be a hard idea to wrap my brain around so to speak.
I immediately thought of Euclid's five postulates. For years people thought that the fifth, parallel, postulate could be derived from the other four. That held for about 2100 years until a couple of boffins found used two different negations of the fifth to derive entire geometries. Applying that to this, I would suppose that if it were possible to encode Euclid's first four postulates into quantum states, and ask whether there was exactly one line parallel to another through a point not on the second line, then the result would sometimes be yes and sometimes no.
-Loyal
I aim to misbehave.
Not prove in the mathematical sense, but show that the statements are true with arbitrarily high probability. It is akin to determining the area of the circle using Monte Carlo method. The law of large numbers guarantees that you will get the correct result if you invest infinite time.
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.
Peer-reviewed journals print things like this all the time. It doesn't mean it is correct or deep.
There... fixed that for you. You aren't incorrect, but your statement indicates a bias against information based on its source. That's an ad hominem argument, and is logically unsound. If you spot a problem in the paper, point it out.
That would be a causal observer.
-
Did many boffins die to bring us this information?
kurzweil_freak
5th Kyu Genbukan Ninpo/KJJR student
Be the darkness that allows the light to shine.
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.
It's actually not an ad hominem argument. The plea was to "not get too excited" and the reason given was the track record of the source. No claim about the accuracy of the paper was made, either way. Before anybody opens up some 12 year old scotch, that author of the paper must successfully defend it.
Fascism trolls keeping me up every night. When I starts a preachin', he HITS ME WITH HIS REICH!
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
He didn't assert that it must be incorrect, he said that it may not be correct. It's not an ad hominem to be suspicious of a source.