You can’t determine compressibility by a computable decision procedure, but the paper outlines why the approximation you can do computably is still good enough.
But I’m interested in the purely information-theoretic question, so I’m perfectly willing to grant even the ability to go ahead and uncomputably determine whether a string is compressible (to within some bounds using some particular programming language). But I don’t yet understand the bits I asked about.
Actually, the second isn’t. I was trying to shortcut Yurtsever’s argument, and that was a slip: the two strings are equivalent if Alice and Bob measure along the same (or opposite) axes only. Nevertheless, both are related in as much as the probability that the measurements the two make agree goes with the cosine squared of the angle between the measurement axes; so the statistics should agree nevertheless (i.e. if Bob’s string is incompressible, then so is Alice’s).
As for the first, think about what it means for a string to be compressible: if the outcome of a sequence of measurements, represented by some string m with |m| = N bits, were compressible, then there exists some universal Turing machine U and a string n with |n| < |m| (there’s an issue with a constant factor c that should be put in here, owing to the freedom of choice of Turing machine and hence the non-uniqueness of the algorithmic complexity measure, but that becomes negligible in the large N limit and I’ll just leave it out), such that U(n) = m (n essentially amounts to hidden variables in this case, so assuming compressibility of measurement outcomes is equivalent to hidden variables). If T is now our randomness generator, there is by definition no string smaller than T that any Turing machine can use to reproduce it.
After now measurement with the scrambled axes has been carried out, we get a new string, m’. If now m’ still is compressible, there is again U’ and n’ such that U’(n’) = m’, |n’| < |m’|. However, m and m’ determine T: Let’s say that the prescription is to either keep the axis, if there is, say, a 1 in T, or flip it for 0, then, whenever there is an agreement in the same position in m and m’, measurement was conducted along identical axes, and the relevant bit in T was 1, and when there is a disagreement, the measurement axis was flipped, and the relevant bit in T was 0.
But then, n and n’ also determine T, since they determine m and m’! Thus, there exists yet another Turing machine U’’ such that U’’(n,n’) = T. But there’s no lower bound on the length of (n,n’); in particular, it may well be below |T|. However, by T’s incompressibility, this can’t exist. Thus, the only way to stay compatible with T being incompressible is to have m’ be incompressible, as well (if m was compressible). I think. If this doesn’t make any sense at all, in my defence, I was at a wedding yesterday and didn’t sleep too much…
Chronos, your objection is actually covered – it suffices to know an approximation of the halting probability (which is an oracle for the halting problem – actually, the most succinct one, as knowledge of the first n bits of the halting probability suffices to decide whether or not all programs smaller than n bits halt) in order to decide the compressibility reliably enough to establish noisy communication.
What are m and m’? [One is the measurements Bob receives; what’s the other?]
Using a prescription of always having Alice and Bob measure along either the same or opposite axes makes the situation purely classical [it wouldn’t differ from having a program generate opposite bits in sealed envelopes, and then either taking them as is or negating them according to the “axis”], so surely that cannot suffice to establish the result. Or perhaps I misunderstand the setup?
(Well, or perhaps I misunderstand what you mean by “flipped axis”. But I was going from
, and this does not seem non-classical)
I am glad to see you say this. I’ve always been thrown by the use of words like “immediately” and “simultaneously” in the context of entanglement, since simultanaity is relative to reference frames.
I guess the surprise is that there is any reference frame in which the events occur simultaneously. Except when I say this, someone (ahem Indistinguishable) always comes in and says that actually entanglement is not an “effect” involving “events” at all. Which I totally believe but have yet to understand. 
They are both strings of measurements, one without the scrambler, one with. Of course, it’s not really kosher in conventional quantum mechanics to talk about the measurements Bob ‘would have made’ if he hadn’t used the scrambler – it wouldn’t make sense to talk about m if we have measured m’ --, but we’re already talking hidden variables, so we can use m at least in the abstract, since n is what’s fundamental, and m can be calculated from n.
You might think about it as Carl’s measurement, if Bob and Carl share an entangled pair of particles, and Carl always measures along the same axis, while Bob changes his according to the prescription given by T. They might obtain something like this:
Carl/m: 110100101101...
Bob/m': 101101100110...
T: 011001001011...
If Bob hadn’t scrambled, he would’ve gotten the same string as Carl. And you’re right that this situation is essentially classical, you could’ve played the same game with 0s and 1s on cards; but I just wanted to look at a simple case to make it plausible that m’ is random if T is.
Ok. But then returning to the bit that confused me, I don’t see why T being incompressible makes m’ incompressible. For it is certainly possible that both T and m are incompressible, and m’ is compressible. For example, perhaps T = m and m’ is all zeros.
(The only thing I see is that if two out of the three are compressible, then the third is as well, since of course any is just the XOR of the other two)
That m is compressible is the starting assumption of the whole thing – the assumption that quantum mechanics isn’t ‘truly random’.
This part I’m also sort of fuzzy on; it’s possible for a compressible and an incompressible string to have some correlation. For example, let A be an incompressible string, and let B be the same as A on even-numbered bits, and all zeros on odd-numbered bits. Then A and B agree 3/4 of the time, but B is compressible despite A being incompressible.
Ah, good point. I understand this part now… I think.
Except… m is the (opposite of the) string Alice will get no matter what, isn’t it? Since Alice never changes her measurement directions. So doesn’t this amount to assuming Alice’s string will be compressible?
Oh dear, I may be lost again.
Alright, well, if you don’t mind hand-holding me through this (sorry for being so slow!), I’m going to try understanding again, one question at a time:
First question: What goes wrong if I try to use this procedure to effect FTL communication on the classical model of a program generating random bits in pairs of sealed envelopes, to be read straight or negated as one likes?
Perhaps we should go through Yurtsever’s argumentation in full; however, I think I’ll need a good nights sleep before. I’m rather stumbling through all this right now, sorry.
I think that I might have confused you more than necessary with the construction of my example to show the incompressibility of the string Bob obtains by scrambling; this isn’t the same setup you’d use to try and send a message to Alice, as Bob wouldn’t merely measure either along the same axis as Alice or the opposite, but rather, they’d both measure along axes at an angle relative to each other. That way, Alice wouldn’t obtain Bob’s ‘if he hadn’t scrambled’-string m, but, because each of Bob’s measurements would put the system into an eigenstate of his measurement, she’d get a string of her own.
No problem; I’d like to return to this whenever you’re up for it.
(I’ve read the Yurtsever paper now, but I guess the details that confuse me haven’t been addressed explicitly enough in it for me to grasp yet)
Yes this is the same problem I have understanding it. Information. theory is not my strong point so talk of ‘p-incomphressibilty’ goes over my head a bit.
If the situation is purely classical then Alice’s string’s p-incompressiblty should be independent of Bob’s string’s p-incompressibilty when he uses his random number generator and the same otherwise.
I think what he’s arguing is that in the quantum situation the correlation (due to entanglement) between the two strings is such that if Bob’s string passes his test for p-incompressibality (for his value of p) then Alice’s string is almost certain to pass her test for p-incompressabilty (for her value of p).
Sorry I never got back to this thread, but I didn’t have my mind in the right order to go over the argumentation in full… Anyway, I’m gonna go on vacation for a week, just wanted to say that I haven’t completely forgotten about the thread; I’ll try to keep the subject in the back of my head. Right now, my hunch is that the randomness of Alice’s bit string in the case of the randomness of Bob’s is due to the fact that the non-random bit strings form a measure-zero subset of the set of all bit strings (hmm, this might only be true for infinite bit strings: the non-random bit strings are a subset of the computable strings, of which there are only countably many, yet the set of all (infinite) bit strings is isomorphic to the reals and hence uncountable), so that when you start out with a random bit string, any arbitrary manipulation almost surely leads to another random bit string. Well, this is probably much more of a waffle than anybody’s gonna let me get away with… But still. Vacation now!