GoKawiilDisclaimer: no AI was used to write this. Any errors, awkward sentences, and weird tangents are 100% organic, free-range, and human-made.
Picking up a puzzle I left lying around
Last post, right at the end, I dropped a puzzle and walked away from it. Here it is again, because this whole post is basically me refusing to let it go.
Imagine two files, and each one holds a million digits. The first one is pure noise — imagine I rolled a ten-sided die a million times and wrote down the results. The second one is the first million digits of π \pi π.
Now look at them the way a statistician would: count how often each digit from 0 0 0 to 9 9 9 shows up. In both files, every digit appears about a tenth of the time, so if you plot the two histograms you cannot tell them apart — both flat, both featureless. And you can run any “is this random?” test you like, because both files will pass. By every statistical measure, these two files are the same: both look like pure, incompressible randomness.
And yet.
One of these files I can send you in three lines. I write you a tiny program — “compute π \pi π, print a million digits” — and you regenerate the file exactly. The other file I cannot shrink at all, and to send it to you I have to send the whole thing, digit by digit, because there is no shorter description of it than itself.
So here is the entire post in one question:
If the two files are statistically identical, why can I compress one and not the other?
The thing is, this question does not have a simple answer, and I think that is exactly what makes it interesting. To get anywhere with it, we have to be careful about what the word “compressible” actually means — and once we are careful, it splits into two very different ideas. Most of this post is about pulling those two apart, and about a surprise waiting at the end of the second one: a kind of compressibility that you can always confirm when it is there, but can never rule out when it is not.
... continue reading