THE FOLD / GLITCH / RACE CONDITION / THE KOLMOGOROV
THE KOLMOGOROV
why most strings cannot be compressed
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Kolmogorov complexity measures a string by the length of the shortest program that prints it. A string is incompressible (or “random”) if no program is much shorter than the string itself. The key fact is a pure counting argument: there are only 2m − 1 possible descriptions shorter than m bits, so at most that many strings can be compressed below m bits. Therefore, among the 2n strings of length n, at least a fraction 1 − 2−c cannot be compressed by even c bits. Most strings are incompressible — randomness is the rule, structure the exception.
LIT verified live: the count of descriptions shorter than n − c bits is exactly 2n−c − 1, always fewer than 2n, so at least (1 − 2−c) of all n-bit strings are c-incompressible; and a real run-length coder fails to shrink almost every random string (window.__kolmogorov). FIG honest: the counting bound is exact; the concrete compressor illustrates it (true Kolmogorov complexity is uncomputable).
LIT verified live: the count of descriptions shorter than n − c bits is exactly 2n−c − 1, always fewer than 2n, so at least (1 − 2−c) of all n-bit strings are c-incompressible; and a real run-length coder fails to shrink almost every random string (window.__kolmogorov). FIG honest: the counting bound is exact; the concrete compressor illustrates it (true Kolmogorov complexity is uncomputable).
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at race-condition — there simply are not enough short programs to name all the strings, so most strings have no short description; the shortage is unavoidable. AVAN (AI) built the instrument: the description-counting bound (2m − 1 short programs), the incompressible-fraction 1 − 2−c, and a run-length compressor on random strings.
Credit as content: Andrey Kolmogorov (1963); also Ray Solomonoff and Gregory Chaitin. The weave: David names race-condition; I count how many strings could possibly have a short description — far fewer than exist — and confirm that a genuine compressor leaves nearly every random string no smaller. Not enough programs to go around.
Credit as content: Andrey Kolmogorov (1963); also Ray Solomonoff and Gregory Chaitin. The weave: David names race-condition; I count how many strings could possibly have a short description — far fewer than exist — and confirm that a genuine compressor leaves nearly every random string no smaller. Not enough programs to go around.
3 ONE DIMENSION
2n strings, but only 2n−c − 1 descriptions shorter than n − c bits. So < 2−c of strings compress by c bits: 1/2 by 1 bit, 1/1024 by 10 bits. Randomness dominates.
4 TWO DIMENSIONS · INTERACTIVE
The counting bound: strings vs short descriptions; the incompressible fraction; a compressor on random strings; checked.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: strings with no short description.
AVAN’s addition (the inverse-companion): don’t look for the pattern in a string — count the programs that could describe it, and find there are too few to compress most strings at all. The inverse of ‘compress this data’ is ‘there aren’t enough short programs, so most data is incompressible.’ Magenta is the rare compressible string; green is the incompressible majority. Not enough programs to go around.
LIT Genuine Kolmogorov complexity (Andrey Kolmogorov, 1963; also Solomonoff and Chaitin). Verified live: the count of binary descriptions shorter than n−c bits is exactly 2^(n−c)−1, always fewer than 2ⁿ, so at least (1−2^(−c)) of all n-bit strings are c-incompressible (window.__kolmogorov.counting); and a run-length coder shrinks only a small fraction of random 32-bit strings (window.__kolmogorov.rleFrac).
FIG No framing: the description-counting bound (2ᵐ−1 short programs), the incompressible-fraction 1−2^(−c), and a run-length compressor on random strings all run in-browser. Honest scope: the counting bound is exact; the concrete compressor merely illustrates it, since true Kolmogorov complexity is uncomputable. The AVAN inverse is honest — counting the programs that could describe a string (too few to compress most) rather than hunting a pattern inside it is the incompressibility argument; magenta is the rare compressible string, green the incompressible majority. Not enough programs to go around.
FIG No framing: the description-counting bound (2ᵐ−1 short programs), the incompressible-fraction 1−2^(−c), and a run-length compressor on random strings all run in-browser. Honest scope: the counting bound is exact; the concrete compressor merely illustrates it, since true Kolmogorov complexity is uncomputable. The AVAN inverse is honest — counting the programs that could describe a string (too few to compress most) rather than hunting a pattern inside it is the incompressibility argument; magenta is the rare compressible string, green the incompressible majority. Not enough programs to go around.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of RACE CONDITION · David Lee Wise (ROOT0), with AVAN