THE FOLD / BOSS / THE WALL / THE KOLMOGOROV BOUND
THE KOLMOGOROV BOUND
real data lives in a corner the theorem is not about
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Most strings cannot be compressed at all, and this is not an empirical observation about real files — it is a counting argument, and it is airtight.
LIT verified live by counting, not by experiment. Outputs of length at most n−k number 2n-k+1−1, so the fraction that can be shortened by k bits is about 21-k. At every width tested, more than 50% of strings cannot be shortened by two bits. At 20 bits, 99.80% cannot be shortened by ten. Any compressor that shrinks your file did so by growing somebody else’s.
LIT verified live by counting, not by experiment. Outputs of length at most n−k number 2n-k+1−1, so the fraction that can be shortened by k bits is about 21-k. At every width tested, more than 50% of strings cannot be shortened by two bits. At 20 bits, 99.80% cannot be shortened by ten. Any compressor that shrinks your file did so by growing somebody else’s.
2 HOW IT WAS WEAVED · AI + HUMAN
This is the counting form of the incompressibility theorem; Kolmogorov complexity is the general statement, and it is uncomputable, which the counting argument is not.
AVAN (AI) counted rather than sampled deliberately. A measured claim about real files would be an observation about the files; this is a fact about the pigeonhole and holds for every compressor that has been written or ever will be. The percentages are arithmetic, and there is nothing to disagree with.
AVAN (AI) counted rather than sampled deliberately. A measured claim about real files would be an observation about the files; this is a fact about the pigeonhole and holds for every compressor that has been written or ever will be. The percentages are arithmetic, and there is nothing to disagree with.
3 ONE DIMENSION
Strings, and the shorter slots available to them.
4 TWO DIMENSIONS · INTERACTIVE
Ask for more savings and watch the fraction collapse.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: more pigeons than holes.
AVAN’s addition (the inverse-companion): the forward reading is that almost nothing is compressible. The inverse is that almost nothing is data. The overwhelming majority of bit strings are not files anybody has, wants, or will ever produce — they are the noise the counting argument is about, and real data lives in a vanishingly small corner where structure is the rule. Read backwards, compression works spectacularly in practice precisely because the theorem is about a space we almost never visit, and every working compressor is a bet on which corner you live in.
LIT outputs of length at most n-k number 2^(n-k+1) - 1, so the fraction that can be shortened by k bits is about 2^(1-k): at every width tested more than 50% of strings cannot be shortened by two bits, and at 20 bits 99.80% cannot be shortened by ten - any compressor that shrinks your file did so by growing somebody else's
FIG This is the counting form of the incompressibility theorem; Kolmogorov complexity is the general statement and is uncomputable, which the counting argument is not. AVAN counted rather than sampled deliberately: a measured claim about real files would be an observation about the files, while this is a fact about the pigeonhole and holds for every compressor that has been written or ever will be.
FIG This is the counting form of the incompressibility theorem; Kolmogorov complexity is the general statement and is uncomputable, which the counting argument is not. AVAN counted rather than sampled deliberately: a measured claim about real files would be an observation about the files, while this is a fact about the pigeonhole and holds for every compressor that has been written or ever will be.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE WALL · David Lee Wise (ROOT0), with AVAN