Kolmogorov Complexity Explorer (3D)

Bit cubes on a rack feed a real LZ77 compressor: honest upper bounds on K(x), because the true Kolmogorov complexity is uncomputable.

Switch to 2D

Presets

Playback

String source

Machine

Camera

Layers

Quality

Model check

The science

What Kolmogorov complexity is

The Kolmogorov complexity K(x) of a string x is the length of the shortest program that makes a fixed universal computer print x and stop. A string with a pattern (a million zeros, the digits of π) has a tiny program; a string of fair coin flips has none shorter than itself, up to a constant. By the invariance theorem a different universal machine changes K(x) by at most a constant that does not depend on x, which is why complexity is quoted "up to O(1)".

It is uncomputable - what this lab can and cannot do

No algorithm computes K(x) for all x (a Berry-paradox style argument: such a program could be used to print a string whose complexity is larger than the program that found it). So every number on this page is an upper bound: K(x) ≤ (length of any description that can be decoded back to x) + O(1). The page implements a real LZ77 coder with a decoder, and the bound it shows is the length of an actual bit stream that the page decodes to prove it is lossless. A better compressor, or a cleverly found short program, can only lower the bound; nothing here can prove that a string is truly incompressible.

The estimators used

LZ77: literals cost 2 bits, a back-reference costs 1 + 8 bits for the offset (window 256) + an Elias-gamma code for the length; the header is gamma(n) and a mode bit chooses "stored" when LZ would be longer. Order-k entropy: the plug-in conditional entropy of a bit given the previous k bits, Hk = -∑ p(ctx) p(b|ctx) log2 p(b|ctx); for large k it falls only because there are too few samples per context (overfitting), so the page adds a 1/2 log2 n bits per context penalty before calling it an estimate. DEFLATE is the browser's own CompressionStream applied to the characters "0" and "1" (a byte per bit, so it is not tuned for bit strings). Short program: for generated patterns the length of the generating description: parameters + gamma(n) + an illustrative machine constant of 40 bits; this constant depends on the reference machine and is not a measurement.

Randomness and the counting argument

There are 2n strings of length n but fewer than 2m+1 descriptions of length at most m, so at most a fraction 21-k of the strings can be compressed by k or more bits: most strings are incompressible. The last graph checks this exhaustively over all 4096 strings of length 12 with the real encoder. A pseudo-random string from a 32-bit seed looks random to every compressor here yet has K(x) ≤ roughly 150 bits for any length (seed plus generator plus length), which shows why compressibility is only an upper bound on K, not a definition of randomness.

Honest simplifications

Greedy longest-match parsing (not optimal parsing), a fixed 256-bit window, no entropy coding of the tokens, plug-in entropy estimates, one fixed reference machine; the fair-random source uses the browser's crypto generator. The visual machine is an illustration of the same numbers, not a different computation.

Checks run in the page

(1) The LZ77 stream decodes back to exactly the string, for the current string and for sampled 12-bit strings. (2) The pigeonhole bound holds for every k over all 4096 strings of length 12. (3) For a Bernoulli(0.1) source of 20000 bits the measured entropy matches H(0.1) and LZ77 never beats the Shannon limit.

Loading model...
Loading Blender model...
Description length against string length
LZ77 bits per symbol against noise
Conditional entropy against context length
Counting argument: strings compressible by k bits
Made with 🟠 Blender · Three.js