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)."

QUNATUM FIRST POST

this may or may not be first post, but one thing is for certain: you suck.

My take on it

In this paper, we will consider mathematical undecidability in certain axiomatic systems which can be completed and which therefore are not subject to Goodel's incompleteness theorem.

[snip]

Now we show that the undecidability of mathematical propositions can be tested in quantum experiments. To this end we introduce a physical "black box" whose internal configuration encodes Boolean functions.

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

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.

Re:My take on it

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.

Sheesh

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:Sheesh

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.

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

It is still overblown

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.

Re:Sheesh

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.

Re:Sheesh

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.

Theory versus reality

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?

A physicist's take

I'll try and give a simplified version of the idea from my understanding of the article.

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:Umm

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.

Re:Umm

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.

Re:Umm

Does this also mean we could also prove theorems by physical experiment?

Re:Umm

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.

Re:Umm

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.

Re:Umm

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.

Re:Umm

Didn't Rush have a song about this?

Re:Umm

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... :\

Re:Umm

They most certainly DO [youtube.com] sell lobster, but periodically. However, you're right, nobody buys it, because it's disgusting.

Re:Umm

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

Re:Umm

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.

Re:Huh, I wonder why no one thought of that before

Seems intuitively obvious to the casual observer

Ah, but now you've changed it again. ;-)

Cheers

Re:Huh, I wonder why no one thought of that before

That would be a causal observer.

Re:They need a quantum test for this?

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.