You're absolutely right about the impossibility of transmitting information FTL using quantum entanglement, but I have a small nitpick about this:
It is effectively the same as writing a random number down on two bits of paper.
It's effectively the same if you're only talking about the ability to send information FTL; but not when talking about other things (like channel capacity). For example, you can use entanglement to double the capacity of a classical channel:
The geometric orientation (i.e., pointing north, east, up, left, etc.).
Suppose you're measuring an electron spin. If you measure it in the "vertical" axis (for some definition of "vertical"), the spin may be "up" or "down". But you can also measure it in the "north" direction (for some definition of "north"), then the result can be "north" or "south".
The thing is: when Alice measures her "coin" in the vertical axis, Bob's coin will have its state defined in this axis. But when Bob measures his coin, he may choose other axis to measure it. Depending on the axis Bob chooses, the result may be different, the difference is exactly described by quantum mechanics.
There's a clever way to exploit this difference to show that it really matters whether Alice measured her "coin" and just kept it secret or if she didn't measure it at all (quantum cryptography, for instance, is based on this).
(...) Anyhow, that's the rampant conjecture that happens with me, and where it gets mysterious. (...)
Look, we believe that quantum mechanics is that way because of what happened in the history of modern Physics. Among other things:
In 1935, Einstein published a paper (with some other people) proposing a thought experiment that showed that Quantum Mechanics predicted a "spooky action at a distance", and so QM was bullshit. (This is usually known as the "EPR paradox")
In 1964, John Bell published a paper with a slightly different thought experiment showing that QM predicted a certain result that was completely incompatible with what "common sense" predicted. Thus, either common sense or QM was wrong. (This is usually known as "Bell's Inequalities")
Later, experimental physicists were finally able to build equipment to actually perform the experiments, and the results shown that nature doesn't care about your common sense: QM is right, common sense is wrong. These experiments were reproduced many times, in many different ways, always showing that nature behaves the way QM predicted.
Now, the way QM is usually explained makes it look like a lot of unnecessary bullshit, and that's mainly the fault of journalists and some physicists that thy to over-simplify things.
If you actually read the math of basic QM, it doesn't have any of the "rampant conjectures" you mentioned, it simply describes the way nature works. When you try to fit it into your common sense of what should be happening is that you end up with these insane ideas.
Is there a practical difference between the two examples?
Yes, there is. Physicists would not simply make a more complicated theory just because it's nicer; they do it because it's the only way to explain what happens.
When you measure the "coin", you must choose the orientation for the measurement. The orientation you choose changes the state of the other (entangled) "coin" -- the state becomes the same you measured *in the same orientation*. If you measure the other "coin" in another orientation, you may have a different result that will depend on the orientation of the first measurement. The exact way the second measurement depends on the first one is described by quantum mechanics.
Now Alice opens her envelope and sees tails. So she knows Bob must have heads. (...) Alice only has access to the information she *brought* with her when they separated.
That's correct, but that's not the whole story. From what you said, it looks like classic mechanics is good enough to explain it, and it's not.
The problem is that there is not only one way you can measure the state of this "coin" -- depending on the orientation of your measurement, you get heads or tails on that specific orientation. So, when Alice measures the coin in a specific orientation, this *orientation* is "felt" by Bob's coin, and it may influence the result of Bob's measurement. That effect simply can't be explained by classic mechanics.
I was actually referring to 4-byte longs on 32-bit platforms. A 32-bit long on a 64-bit platform would violate the spec.
Oh, sorry about the confusion -- yes, you're right. But if you're just worrying about the size of integers, C99 has int64_t (and many compilers that don't fully support C99 have it, even Visual C++). But I agree that the situation is far from ideal.
I am not an expert in the vagaries of memory access, but I see no reason why a 2 dimensional array could not hold the same amount of data as a 1 dimensional array with a long index.
Well, it could -- but it your problem really wants a single-dimensional array, it's an ugly hack to use a two-dimensional array to "simulate" it. Imagine writing:
for every single array access. Yes, you could create a class to encapsulate such accesses, but array access REALLY belongs to the language, and not a library.
Well, saying "often" might be an exaggeration; the only major 64-bit compiler where a long is 32-bit is Visual C++. Every other 64-bit C compiler I've seen or heard of is LP64 (meaning a long is 64-bit) -- Linux (gcc), FreeBSD, Solaris, Mac OS X (also gcc), AIX, HP.
As for Java, the real problem is that you simply can't index an array with a long, so you're limited to 31-bit indices. It might seem crazy to have arrays with more than 2 billion entries today, but when we start to have hundreds of gigs of memory, it will be useful. I wonder if Java will ever change this.
Ah, so your problem is not with physics, but with probability.
The thing is, there's no "abandoning of what is mathematically provable" in studying probabilistic algorithms. Computer science has studied for decades complexity classes like BPP (bounded-error, probabilistic, polynomial time) which contains many useful algorithms, like for instance the Miller-Rabin primality test, which is used by OpenSSL to check if a number is prime.
So, whether you like it or not, it's already part of computer science.
Any hopes for a speed-up on Automated-Theorem-Proving?
Automated theorem proving (using propositional calculus) is NP-complete, so it's the same "no, to the best of our knowledge". (Using first order predicate calculus is even worse -- the algorithm is not even guaranteed to terminate).
A nitpick to avoid confusion: the above comment is talking about the efficiency of computers. So, you should read
Quantum computers solve problems in BQP.
as "Quantum computers efficiently solve problems in BQP" (that is, by the way, the definition of BQP). Ditto for the following paragraph: "we do not know if a quantum computer can efficiently solve any problems a classical computer (with a random source) can't (solve efficiently)."
It also seems a little nonsensical to ask if a quantum computer can solve P=NP. "P=?NP" is a mathematical question, so this is like asking if a quantum computer can prove Fermat's Last Theorem. I think the parent poster sensibly interpreted the question as "does this mean quantum computers can (efficiently) solve NP-complete problems? (That is, does BQP contain NP?)".
If you think quantum computing is about putting a physical system in a certain state and manipulating it, then you should also think classical computing is about setting a tape in a certain way and manipulating it.
When Turing first described a computer (a turing machine), it was essentially a mechanism where you put a tape in a certain state, manipulate it according to certain rules and in the end you get the tape in another state containing the "result" of your computation. What was so interesting about it it that it was theoretically possible to build a machine that would be able to do the manipulations automatically.
Quantum computation is analogous: get a certain vector in an n-dimensional Hilbert space, multiply it by these certain matrices in this specific order, and in the end you get a vector that corresponds to the "calculation" you did. This is absolutely only math, it has nothing to do with physics. What's exciting about this is that we expect to be able to build (real) machines that perform these operations way faster than any computer today can, because the specific operations with which be built our algorithm are exactly the things nature is capable of doing fast.
Of course, we only discovered this when we discovered quantum mechanics -- that's the relation to physics.
I'm not a physicist, but I'm studying QM -- mainly the mathematics of it (I guess what you called the "Hilbert-space-ness":-)).
But I'm also very interested in its interpretations. Am I correct in assuming you subscribe to the Bohm interpretation? (It seems to be the only one I know of that agrees with what you said.) If so, how do you reconcile it with the EPR paradox? To me, saying the orientation of the measurement apparatus affects the wavefunction is as magical as saying the wavefunction collapses. What's your take on it? I'm not criticizing, I'm just curious...
Thank you for pointing out my egregious errors. So let me say what I should have said: every proposition of *propositional calculus* is provably true or false. That is a counterexample to the incorrect statement of Godel's first incompleteness theorems above. I've no idea how I drifted from propositional calculus to first order logic and on a good day I'm fully aware that Godel uses two different sense of completeness - after all, I've read the same book as you.
No problem:-). This is one of those subjects that it is very easy to misremember something if you don't work with it often. When I read your post, I went back to that book to write my reply:-)
A sad story about that book. I read it on the recommendation of the author himself. He said I should get back to him if I had any questions. So I compiled my list of questions and got ready to send it to him. And then I found he'd died of bone cancer. It's a great loss to the world.
Whoa... I didn't know he had died. A great loss, indeed.
> it's kind of a cheat to have infinitely many axioms without a production rule...
Absolutely. That's the whole point of Godel's (incompleteness) theorems. If you fail to mention the production rule then you're talking about the wrong thing.
Not quite. Soundness is the converse of Completeness (in this sense, NOT in the sense of the Incompleteness Theorem):
Completeness (in the sense of the Completeness Theorem): if it follows by reasoning (i.e., it is "true"), it is also provable applying first order logic to the axioms.
Soundness: if it is provable using first order logic to the axioms, it also follows by reasoning (i.e., it is "true").
It's important to note that First Order Logic is not an axiomatic system per se, it is only a way to derive propositions. Therefore, it is not subject to be Complete or Incomplete in the sense of the Incompleteness Theorem.
Perhaps there's a confusion with First Order Theory, which is a set of axioms and their derivation using First Order Logic -- the choice of axioms defines which FOT you're talking about, for example Peano Arithmetic or ZFC. These can be Complete or Incomplete in the sense of the Incompleteness Theorem (and indeed are Incomplete).
We already know that a statement like the continuum hypothesis can be proved neither true nor false from ZFC. We don't need Godel's theorem to prove "incompleteness or inconsistency" when we have lots of practical examples of its incompleteness. So your claim of "don't know" is false.
Well said. As another example, the "C" of ZFC (axiom of choice) is independent of ZF.
First order logic is consistent and complete. In fact, Godel proved this.
No, he didn't. This is a common misconception because of the name of his "Completeness Theorem".
The "Completeness Theorem" simply states that whatever you can prove (syntactically) with first order logic within a system is exactly what you would accept (intuitively) as true. This is important because it guarantees that if you apply first order logic within a set of (true) axioms, you can only reach things you would normally accept as true; and conversely, if you reason using only the axioms, you can write down your reasoning using first order logic. So, it is only in this sense that first order logic is "complete".
The Wikipedia article on it (here) makes the distinction clearly, stating that the "completeness" of one theorem is of a different kind than the other, but I recommend this book (sorry, Amazon link), which explains it way better (and much more clearly).
Additionally, consider the set S of all possible propositions of set theory. Somewhere in the power set of S must lie the set of all true propositions. Just take these as your axioms. Voila, a formal system that is both complete and consistent. Your characterization of Godel's theorem is incorrect.
Well, sure, but it's kind of a cheat to have infinitely many axioms without a production rule... How exactly do you know what are the axioms (i.e., which element of the power set of S to take)?:-)
[...] To implement that, all we lack is the ability to store unbounded information in a world of finitely many atoms.
Well, even if we had infinitely many atoms, we would still have problems. The Schwarzschild bound limits the amount of energy that can be stored in a volume of space before creating a black hole. So, unless you create a magical way to store information without wasting energy, there's a limit on the amount of information you can store in a given space. Still, this is only a problem if you don't want to wait forever: if you allow unbounded space, the time of computation will be unbounded (because information can't propagate faster than the speed of light).
Can intelligence do something more than Turing machines?
Well, that's still very much an open question, but notice that we (humans) can't seem to think of anything better than Turing machines, at least not yet. Even quantum computers only offer better efficiency; they are still capable of solving exactly the same problems than a Turing machine.
Slashdot Mirror
Paul Dirac's 'Principles of Quantum Mechanics'
I absolutely agree -- this is a GREAT book.
Although, to be fair, it should be said that it requires a bit of math above what's required by the other books mentioned in the question.
Google books has a limited preview: http://books.google.com/books?id=XehUpGiM6FIC&printsec=frontcover
You're absolutely right about the impossibility of transmitting information FTL using quantum entanglement, but I have a small nitpick about this:
It's effectively the same if you're only talking about the ability to send information FTL; but not when talking about other things (like channel capacity). For example, you can use entanglement to double the capacity of a classical channel:
http://www.quantiki.org/wiki/index.php/Enhancement_of_channel_capacities_with_entanglement
(and also http://en.wikipedia.org/wiki/Superdense_coding)
This could never be done with the two bits of paper.
The geometric orientation (i.e., pointing north, east, up, left, etc.).
Suppose you're measuring an electron spin. If you measure it in the "vertical" axis (for some definition of "vertical"), the spin may be "up" or "down". But you can also measure it in the "north" direction (for some definition of "north"), then the result can be "north" or "south".
The thing is: when Alice measures her "coin" in the vertical axis, Bob's coin will have its state defined in this axis. But when Bob measures his coin, he may choose other axis to measure it. Depending on the axis Bob chooses, the result may be different, the difference is exactly described by quantum mechanics.
There's a clever way to exploit this difference to show that it really matters whether Alice measured her "coin" and just kept it secret or if she didn't measure it at all (quantum cryptography, for instance, is based on this).
(...) Anyhow, that's the rampant conjecture that happens with me, and where it gets mysterious. (...)
Look, we believe that quantum mechanics is that way because of what happened in the history of modern Physics. Among other things:
In 1935, Einstein published a paper (with some other people) proposing a thought experiment that showed that Quantum Mechanics predicted a "spooky action at a distance", and so QM was bullshit. (This is usually known as the "EPR paradox")
In 1964, John Bell published a paper with a slightly different thought experiment showing that QM predicted a certain result that was completely incompatible with what "common sense" predicted. Thus, either common sense or QM was wrong. (This is usually known as "Bell's Inequalities")
Later, experimental physicists were finally able to build equipment to actually perform the experiments, and the results shown that nature doesn't care about your common sense: QM is right, common sense is wrong. These experiments were reproduced many times, in many different ways, always showing that nature behaves the way QM predicted.
Now, the way QM is usually explained makes it look like a lot of unnecessary bullshit, and that's mainly the fault of journalists and some physicists that thy to over-simplify things.
If you actually read the math of basic QM, it doesn't have any of the "rampant conjectures" you mentioned, it simply describes the way nature works. When you try to fit it into your common sense of what should be happening is that you end up with these insane ideas.
Is there a practical difference between the two examples?
Yes, there is. Physicists would not simply make a more complicated theory just because it's nicer; they do it because it's the only way to explain what happens.
When you measure the "coin", you must choose the orientation for the measurement. The orientation you choose changes the state of the other (entangled) "coin" -- the state becomes the same you measured *in the same orientation*. If you measure the other "coin" in another orientation, you may have a different result that will depend on the orientation of the first measurement. The exact way the second measurement depends on the first one is described by quantum mechanics.
Now Alice opens her envelope and sees tails. So she knows Bob must have heads. (...) Alice only has access to the information she *brought* with her when they separated.
That's correct, but that's not the whole story. From what you said, it looks like classic mechanics is good enough to explain it, and it's not.
The problem is that there is not only one way you can measure the state of this "coin" -- depending on the orientation of your measurement, you get heads or tails on that specific orientation. So, when Alice measures the coin in a specific orientation, this *orientation* is "felt" by Bob's coin, and it may influence the result of Bob's measurement. That effect simply can't be explained by classic mechanics.
For a more detailed explanation, see the section on Bell's Inequality in http://www.eecs.berkeley.edu/~vazirani/f04quantum/notes/lecture1.pdf (warning: requires a bit of math).
sorry to break it to you but the set of even primes is quite small.
True, an even prime is really odd.
SOMEONE CALL A DOCTOR!!
There's a guy choking here!
From what I can tell, Microsoft is indeed doing system programming in C#.
What's your source? I kind of doubt it because of things like these.
I hate MS as much as the next guy, but I think you're being unfair. Microsoft (eventually) fixes all security flaws they know about.
And, to make the analogy completely fair: most locks can be picked.
I was actually referring to 4-byte longs on 32-bit platforms. A 32-bit long on a 64-bit platform would violate the spec.
Oh, sorry about the confusion -- yes, you're right. But if you're just worrying about the size of integers, C99 has int64_t (and many compilers that don't fully support C99 have it, even Visual C++). But I agree that the situation is far from ideal.
I am not an expert in the vagaries of memory access, but I see no reason why a 2 dimensional array could not hold the same amount of data as a 1 dimensional array with a long index.
Well, it could -- but it your problem really wants a single-dimensional array, it's an ugly hack to use a two-dimensional array to "simulate" it. Imagine writing:
array[(int) (index >> 31)][(int) (index & 0x7fffffff)]
instead of:
array[index]
for every single array access. Yes, you could create a class to encapsulate such accesses, but array access REALLY belongs to the language, and not a library.
Well, saying "often" might be an exaggeration; the only major 64-bit compiler where a long is 32-bit is Visual C++. Every other 64-bit C compiler I've seen or heard of is LP64 (meaning a long is 64-bit) -- Linux (gcc), FreeBSD, Solaris, Mac OS X (also gcc), AIX, HP.
As for Java, the real problem is that you simply can't index an array with a long, so you're limited to 31-bit indices. It might seem crazy to have arrays with more than 2 billion entries today, but when we start to have hundreds of gigs of memory, it will be useful. I wonder if Java will ever change this.
Ah, so your problem is not with physics, but with probability.
The thing is, there's no "abandoning of what is mathematically provable" in studying probabilistic algorithms. Computer science has studied for decades complexity classes like BPP (bounded-error, probabilistic, polynomial time) which contains many useful algorithms, like for instance the Miller-Rabin primality test, which is used by OpenSSL to check if a number is prime.
So, whether you like it or not, it's already part of computer science.
Any hopes for a speed-up on Automated-Theorem-Proving?
Automated theorem proving (using propositional calculus) is NP-complete, so it's the same "no, to the best of our knowledge". (Using first order predicate calculus is even worse -- the algorithm is not even guaranteed to terminate).
A nitpick to avoid confusion: the above comment is talking about the efficiency of computers. So, you should read
Quantum computers solve problems in BQP.
as "Quantum computers efficiently solve problems in BQP" (that is, by the way, the definition of BQP). Ditto for the following paragraph: "we do not know if a quantum computer can efficiently solve any problems a classical computer (with a random source) can't (solve efficiently)."
It also seems a little nonsensical to ask if a quantum computer can solve P=NP. "P=?NP" is a mathematical question, so this is like asking if a quantum computer can prove Fermat's Last Theorem. I think the parent poster sensibly interpreted the question as "does this mean quantum computers can (efficiently) solve NP-complete problems? (That is, does BQP contain NP?)".
If you think quantum computing is about putting a physical system in a certain state and manipulating it, then you should also think classical computing is about setting a tape in a certain way and manipulating it.
When Turing first described a computer (a turing machine), it was essentially a mechanism where you put a tape in a certain state, manipulate it according to certain rules and in the end you get the tape in another state containing the "result" of your computation. What was so interesting about it it that it was theoretically possible to build a machine that would be able to do the manipulations automatically.
Quantum computation is analogous: get a certain vector in an n-dimensional Hilbert space, multiply it by these certain matrices in this specific order, and in the end you get a vector that corresponds to the "calculation" you did. This is absolutely only math, it has nothing to do with physics. What's exciting about this is that we expect to be able to build (real) machines that perform these operations way faster than any computer today can, because the specific operations with which be built our algorithm are exactly the things nature is capable of doing fast.
Of course, we only discovered this when we discovered quantum mechanics -- that's the relation to physics.
Ah, I see... that makes sense. Maybe it's just me, but it would make a lot more sense than the Bohm interpretation.
Of course, you would still have to show that this nonlinear stuff really exists, and that would be huge.
I'm not a physicist, but I'm studying QM -- mainly the mathematics of it (I guess what you called the "Hilbert-space-ness" :-)).
But I'm also very interested in its interpretations. Am I correct in assuming you subscribe to the Bohm interpretation? (It seems to be the only one I know of that agrees with what you said.) If so, how do you reconcile it with the EPR paradox? To me, saying the orientation of the measurement apparatus affects the wavefunction is as magical as saying the wavefunction collapses. What's your take on it? I'm not criticizing, I'm just curious...
And please stop calling them disks! Disks are cicular objects.
Good luck with that. People still "dial" phones, even though phones with dials haven't existed for decades.
Thank you for pointing out my egregious errors. So let me say what I should have said: every proposition of *propositional calculus* is provably true or false. That is a counterexample to the incorrect statement of Godel's first incompleteness theorems above. I've no idea how I drifted from propositional calculus to first order logic and on a good day I'm fully aware that Godel uses two different sense of completeness - after all, I've read the same book as you.
No problem :-). This is one of those subjects that it is very easy to misremember something if you don't work with it often. When I read your post, I went back to that book to write my reply :-)
A sad story about that book. I read it on the recommendation of the author himself. He said I should get back to him if I had any questions. So I compiled my list of questions and got ready to send it to him. And then I found he'd died of bone cancer. It's a great loss to the world.
Whoa... I didn't know he had died. A great loss, indeed.
> it's kind of a cheat to have infinitely many axioms without a production rule...
Absolutely. That's the whole point of Godel's (incompleteness) theorems. If you fail to mention the production rule then you're talking about the wrong thing.
Agreed.
What you are calling Completeness is Soundness.
Not quite. Soundness is the converse of Completeness (in this sense, NOT in the sense of the Incompleteness Theorem):
It's important to note that First Order Logic is not an axiomatic system per se, it is only a way to derive propositions. Therefore, it is not subject to be Complete or Incomplete in the sense of the Incompleteness Theorem.
Perhaps there's a confusion with First Order Theory, which is a set of axioms and their derivation using First Order Logic -- the choice of axioms defines which FOT you're talking about, for example Peano Arithmetic or ZFC. These can be Complete or Incomplete in the sense of the Incompleteness Theorem (and indeed are Incomplete).
We already know that a statement like the continuum hypothesis can be proved neither true nor false from ZFC. We don't need Godel's theorem to prove "incompleteness or inconsistency" when we have lots of practical examples of its incompleteness. So your claim of "don't know" is false.
Well said. As another example, the "C" of ZFC (axiom of choice) is independent of ZF.
First order logic is consistent and complete. In fact, Godel proved this.
No, he didn't. This is a common misconception because of the name of his "Completeness Theorem".
The "Completeness Theorem" simply states that whatever you can prove (syntactically) with first order logic within a system is exactly what you would accept (intuitively) as true. This is important because it guarantees that if you apply first order logic within a set of (true) axioms, you can only reach things you would normally accept as true; and conversely, if you reason using only the axioms, you can write down your reasoning using first order logic. So, it is only in this sense that first order logic is "complete".
The Wikipedia article on it (here) makes the distinction clearly, stating that the "completeness" of one theorem is of a different kind than the other, but I recommend this book (sorry, Amazon link), which explains it way better (and much more clearly).
Additionally, consider the set S of all possible propositions of set theory. Somewhere in the power set of S must lie the set of all true propositions. Just take these as your axioms. Voila, a formal system that is both complete and consistent. Your characterization of Godel's theorem is incorrect.
Well, sure, but it's kind of a cheat to have infinitely many axioms without a production rule... How exactly do you know what are the axioms (i.e., which element of the power set of S to take)? :-)
Nice post. Some points:
[...] To implement that, all we lack is the ability to store unbounded information in a world of finitely many atoms.
Well, even if we had infinitely many atoms, we would still have problems. The Schwarzschild bound limits the amount of energy that can be stored in a volume of space before creating a black hole. So, unless you create a magical way to store information without wasting energy, there's a limit on the amount of information you can store in a given space. Still, this is only a problem if you don't want to wait forever: if you allow unbounded space, the time of computation will be unbounded (because information can't propagate faster than the speed of light).
Can intelligence do something more than Turing machines?
Well, that's still very much an open question, but notice that we (humans) can't seem to think of anything better than Turing machines, at least not yet. Even quantum computers only offer better efficiency; they are still capable of solving exactly the same problems than a Turing machine.
"perl -pi" alters the processed files, it doesn't send the replaced text to standard output.
I always do "perl -pi.orig ...", though -- it saves the original file with a ".orig" extension.
I think you missed a '$' before the open parenthesis, it should be:
SHELLID=$(echo `tty` | sed 's!/!.!g')
Also, you could replace "echo `tty`" with simply "tty":
SHELLID=$(tty | sed 's!/!.!g')