Slashdot Log In
Quantum Test Found For Mathematical Undecidability
Posted by
kdawson
on Tue Dec 02, 2008 01:25 PM
from the not-to-decide-is-to-decide dept.
from the not-to-decide-is-to-decide dept.
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)."
Related Stories
This discussion has been archived.
No new comments can be posted.
The Fine Print: The following comments are owned by whoever posted them. We are not responsible for them in any way.
Full
Abbreviated
Hidden
Loading... please wait.
QUNATUM FIRST POST (Score:3, Funny)
this may or may not be first post, but one thing is for certain: you suck.
Don't get too excited (Score:2)
Re: (Score:3, Insightful)
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.
Umm (Score:2)
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.
Re:Umm (Score:4, Informative)
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.
Parent
Re: (Score:2, Offtopic)
Good book. LONG read.
Re:Umm (Score:5, Informative)
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.
Parent
Re:Umm (Score:5, Interesting)
Does this also mean we could also prove theorems by physical experiment?
Parent
Re:Umm (Score:4, Insightful)
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 [wikipedia.org]. The law of large numbers guarantees that you will get the correct result if you invest infinite time.
Parent
Re:Umm (Score:5, Informative)
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.
Parent
Re:Umm (Score:4, Interesting)
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.
Parent
Re:Umm (Score:4, Insightful)
Parent
Re:Umm (Score:5, Interesting)
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...
Parent
Re:Umm (Score:4, Informative)
Parent
Re:Umm (Score:4, Interesting)
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
Parent
Re:Umm (Score:4, Informative)
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.
Parent
Huh, I wonder why no one thought of that before (Score:2)
Model formal systems in quantum state encoding; undecidable theorem == uncertain state.
Seems intuitively obvious to the casual observer.
Re:Huh, I wonder why no one thought of that before (Score:5, Funny)
Ah, but now you've changed it again. ;-)
Cheers
Parent
Re:Huh, I wonder why no one thought of that before (Score:5, Funny)
That would be a causal observer.
Parent
Meh (Score:2, Funny)
My take on it (Score:5, Informative)
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.
Re:My take on it (Score:4, Interesting)
The feeling I get from reading this is that it might be possible to offer an interpretation of the Universe as a huge decidability-machine. It's a leap, of course, but might be interesting to explore.
Parent
Re:My take on it (Score:5, Interesting)
Interesting. I think you are onto something here. We can think of a universe as an encoding of a particular axiomatic system, and then there are "facts" in that universe which come up to surface with high probability. To an observer they look like "laws". Moreover, there may be some undecidable propositions which, to an observer, appear like sheer randomness. Also, if the number of qubits in the universe is infinite, it is quite possible that the universe "knows" everything.
Parent
Sheesh (Score:3, Interesting)
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."
Re: (Score:2)
Only for sufficiently small values of 1.
UNITS!!! (Score:3, Insightful)
Re: (Score:3, Funny)
Re:Sheesh (Score:5, Insightful)
No, really, they're serious.
The rules of math (which weren't so much invented as identified) seem oddly linked to the underlying physics. TFA mentions the unreasonable effectiveness of mathematics [wikipedia.org] -- it's not so much that we can count the physics with the math, it's that the math predicts things which should be true, and are subsequently proven to be. The existence of things like a negative square root in an equation have predicted the existence of things like anti-particles, and those particles have been found experimentally.
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 because it goes well beyond simply counting what is, it means the same rules which define the math in the first place underly the physical mechanisms.
Cheers
Parent
Re: (Score:2)
That's a very startling proposition because it goes well beyond simply counting what is, it means the same rules which define the math in the first place underly the physical mechanisms.
But it really isn't startling at all. It's the only way it can be. Physics cannot violate mathematics -- because that's like saying physics might contradict 1 + 1 = 2. Or that physics might somehow cause having 10 bananas, adding 2 bananas, and winding up with 13 bananas.
Mathematics underlies physics because it can't be an
Re: (Score:3, Insightful)
You can't say this and also have previously said "We use mathematics to quantify physics, but there is no "connection" between the two.
Well, you can, but only one can be true.
It's true that the our understanding of physics is tied to the math, but for the math to accurately imply the existence of new phenomena which haven't previously been conceived of speaks more to the fact that the "real" physics obeys t
Re: (Score:2)
But it really isn't startling at all. It's the only way it can be. Physics cannot violate mathematics -- because that's like saying physics might contradict 1 + 1 = 2. Or that physics might somehow cause having 10 bananas, adding 2 bananas, and winding up with 13 bananas.
This is actually an assumption: You are assuming that your logical system (forgot the technical term, sorry, don't have Enderton in front of me) of arithmetic is the same as your model (remembered that one at least ;-) ). Which may or may not be true.
Re: (Score:2)
It is still overblown (Score:5, Insightful)
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.
Parent
Re: (Score:2)
That's only word playing.
There's no more 'existence' in a negative square root, than to a positive one. You have to define what 'existence' means, and only then we can decide if there's some relation between anti-particles and negative square roots.
It's a false dicothomy to talk about math and 'physics' as separate things.
Re: (Score:3, Informative)
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-par
Re: (Score:2)
I think they're just saying that it's interesting to explore which bits of mathematics end up being relevant to physics and which don't. For instance, I doubt anyone in the early 20th century expected number theory to crop up in a physical theory, but it did. Likewise, few people anticipated that quantum computing had interesting theoretical properties to it that differ from classical computing.
Re:Sheesh (Score:5, Insightful)
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."
I'm glad you're so sure of yourself. However, the connection between *counting* (ring of integers) and, say, complex conjugation isn't so obvious. If you'd like to compete with Dirac (for example) and argue that he was dumb for taking so long to recognize antiparticles' existence, or that Green should have "obviously" recognized that there must be such things as evanescent waves because the Helmholtz equation has some complex roots for the wavenumbers, then be my guest.
I don't know what your background is, but such connections between mathematics and the "real world" are NOT always obvious, and it is a continued source of delight and puzzlement when one explores some neglected branch-cut in the maths, and it turns out to have real impact on the physics. Please, explain to all of we poor physicists how bananas can point us to truth.
Parent
Re: (Score:2)
If you'd like to compete with Dirac (for example) and argue that he was dumb for taking so long to recognize antiparticles' existence, or that Green should have "obviously" recognized that there must be such things as evanescent waves because the Helmholtz equation has some complex roots for the wavenumbers, then be my guest.
I'm not claiming that anything is obvious, or that the any particular equation automatically describes physical reality. I'm arguing more from the other side -- that it's silly to be
Re: (Score:2)
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.
Well...No, it's not. The famous story is told of the philosopher who was cloud watching. It seems that he saw one cloud, and he saw another cloud. As he watched one cloud approached the other until they got very close to each other and then merged. "What do you know?" declared the philosopher. "1+1=1."
Now, the engineer will immediately object a
Re:Sheesh (Score:5, Insightful)
Mathematics is an abstract game of counting, built up into great complexity.
Mathematics is a game of abstraction, played out in a wide variety of directions, counting being just one of them. The assumption that mathematics is just counting is rather frustrating. Yes, you can reduce mathematics to arithmetic, but then you can also reduce it to set theory, or to topos theory/category theory, and so on. The ability to express things in a particular way does not that that is what the the things are, especially given the profusion of different mutually interpretable "reductions" available.
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.
Actually you can dream up universes where 1+1=2 doesn't hold. It can fail to hold for a variety of reasons. The various hypothetical universes vary with those reasons from completely uninteresting and trivial, through to, well, in this case, still relatively uninteresting. Of course there are other "fundamental truths" that you can drop (the law of excluded middle, for example, or DeMorgan's laws, which are both conceivably more fundamental than 1+1=2) and end up with remarkably rich and interesting universes. The absolute universality of mathematical truth is on rather shaky ground; certainly the mathematics we use seems pretty solid for our universe, but that doesn't make it universal over all possible universes.
We use mathematics to quantify physics, but there is no "connection" between the two
There is a connection to the extent that ideas developed in the abstract for purely mathematical reasons have often had surprising, unseen, and unlooked for applications to physics. It is the surprising aspect of that that makes philosphers question the apparently unreasonable effectiveness of mathematics.
Parent
Re: (Score:3, Interesting)
Actually you can dream up universes where 1+1=2 doesn't hold. It can fail to hold for a variety of reasons.
And down the relativistic shoot we go. Would those reasons be related to physics by any chance? Honestly, I can't see how such an abstract concept such as math could conceivably even hint how 1+1 would not equal 2. If it equals something else, then congratulations, you have created an operator which does not have the quality that simple addition does.
You fail to have enough imagination. As a trivial example of when 1+1=2 doesn't hold, what if addition did not exist? This is not an interesting example, nor can I come up with one that is interesting, but that is what GP said too.
Equally, special numbers such as Pi and e will always output the same pattern of digits in any multi/quasi/supro-uno universe (given a particular base to start with - it doesn't have to be 10 of course).
Ah, something more interesting! Pi only has its familiar value in Euclidean space (which is the space we live in, not so coincidentally). Imagine hyperbolic space, and you have a value for pi that is larger than standard, exactly how much bigger depending on the curvature.
Re: (Score:3, Insightful)
> It's entirely possible and reasonable we can determine universal laws without having the faintest idea of *why* they are that way.
> 1 + 1 = 2 will be true in any universe
Really? I find the opposite is true.
You need to know "why the laws hold" in order to know if the laws are applicable at all.
Take one liter of water and add one liter of alcohol and mix together. I guarantee you won't get two liters of the mixture. Ditto with one liter of matter and one liter of antimatter.
You might say, that you hav
Theory versus reality (Score:3, Insightful)
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?
Re: (Score:2, Informative)
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 fash
And these people laughed at ... (Score:2)
Didn't read the article, but ... (Score:2)
Deep.. or trivial? (Score:2, Informative)
A physicist's take (Score:5, Informative)
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.
Re:They need a quantum test for this? (Score:4, Insightful)
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.
Parent
Re: (Score:2)
So they want to establish a connection (or lack of connection) between physics and the instruction book that we wrote to describe physics?
Good, but I've got a better comparison, they've established a connection between what you see happen in a game of football vs what is in the rule book for football.