EN 
Українська
Polski
Español
Deutsch
日本語
Italiano
Português (BR)
Français
العربية
Nederlands
中文
한국어
हिन्दी
Türkçe
Tiếng Việt
Русский
Bahasa Indonesia
فارسی
বাংলা
ไทย
Filipino
Kiswahili
اردو
Bahasa Melayu
தமிழ்
עברית
Ελληνικά
ਪੰਜਾਬੀ
አማርኛ
မြန်မာဘာသာ
ខ្មែរ
ქართული
नेपाली
Монгол хэл
Հայերեն
සිංහල
ລາວ
Čeština
Română
Magyar
Български
Svenska
Dansk
Suomi
Norsk
Slovenčina
Hrvatski
Српски
Slovenščina
Lietuvių
Latviešu
Eesti
Íslenska
Shqip
Македонски
Bosanski
Malti🧮 Kolmogorov Complexity: The Shortest Description
Compress a bit-string live with a real LZ77-style algorithm and use the compressed length as an honest, computable upper-bound proxy for the (provably uncomputable) Kolmogorov complexity.
About Kolmogorov Complexity
The Kolmogorov complexity K(x) of a string x, formalised independently by Ray Solomonoff, Andrey Kolmogorov and Gregory Chaitin, is the length of the shortest program that outputs x on a fixed universal machine. A string like a thousand repetitions of "01" has low K(x): a tiny program ("print 01, 500 times") generates it. A string that looks like the output of fair coin flips typically has K(x) close to its own length, because no shorter description exists than the string itself. Crucially, K(x) is provably uncomputable — a consequence closely related to the halting problem: no algorithm can take an arbitrary string and output its true minimal program length, because such an algorithm could be used to detect non-halting programs shorter than any given bound.
Because the real quantity is out of reach, this simulation uses a genuine, honestly-labelled computable stand-in: a simplified fixed-width LZ77 compressor that actually runs on whatever bit-string you give it. It slides a window back through the string, finds the longest previously-seen match at each position, and emits a real stream of literal and match tokens. The resulting bit count is a true upper bound on K(x) — never the real value, and never provably tight — but it is enough to make the core intuition concrete: patterned strings compress hard, and strings that look random to this compressor do not compress much at all.
Frequently Asked Questions
What exactly is Kolmogorov complexity?
K(x) is the length, in bits, of the shortest program that, run on a fixed universal computer (a fixed reference machine), outputs the string x and halts. It is a property of the string itself, not of any particular compressor — but it can only be defined relative to a choice of machine, and different machines change K(x) by at most an additive constant (the invariance theorem).
Why is Kolmogorov complexity uncomputable?
If an algorithm could compute K(x) for every x, you could use it to find, for any n, the shortest string whose complexity provably exceeds n — but describing "the shortest string with complexity greater than n" is itself a short description of a supposedly-incompressible string, a contradiction known as the Berry paradox made rigorous. Formally, computing K(x) would let you solve the halting problem, which is impossible. This is a genuine, foundational undecidability result, not an engineering limitation that faster hardware could fix.
If K(x) is uncomputable, what does this simulation actually show?
It shows a real, computable proxy: the length of the output of an actual compression algorithm (a simplified LZ77) running on your string, right now, in your browser. A short compressed length is solid evidence of low complexity — a program that reconstructs the compressed tokens is itself a valid short description. A long compressed length is much weaker evidence: it only shows this particular compressor found no exploitable structure, not that no shorter description exists anywhere.
Why does the "structured" Thue–Morse preset not compress as much as the repetitive preset?
The Thue–Morse sequence (bit n = parity of the number of 1s in the binary representation of n) has a tiny recursive generating rule, so its true Kolmogorov complexity is very low — but it is deliberately overlap-free and avoids long repeated runs by construction. A sliding-window LZ77 compressor mostly matches literal substrings, so it only partially exploits that structure. This is an honest limitation of the proxy: low complexity does not guarantee any particular compressor will find it.
Why does the random preset barely compress at all?
Each bit is drawn independently with Math.random(), so on average there is no repeated substring for the sliding window to exploit beyond what is expected by chance in a short window. The LZ77 output length stays close to the original length, which is exactly the behaviour expected of a Kolmogorov-random (or algorithmically random) string: no substantially shorter description exists.
Is Math.random() truly random?
No — it is a deterministic pseudo-random number generator seeded internally by the browser. For the purposes of this demonstration it behaves statistically like independent coin flips and is a reasonable practical stand-in; a philosophically "truly random" source would need a physical process such as radioactive decay or quantum measurement noise.
How is the compressed length in bits actually computed here?
The encoder emits a sequence of tokens: either a literal bit, or a (offset, length) back-reference to an earlier matching run (minimum match length 3, maximum window 48 bits, maximum match 32 bits). Each token costs one flag bit plus either one literal bit or a fixed number of bits for the offset and length fields, sized to the window and match limits. Summing these costs gives a real, honestly-computed encoded bit length — a simplified relative of the LZ77 stage inside DEFLATE (ZIP, gzip, PNG).
Does a better compressor always get closer to the true K(x)?
A better, smarter compressor (arithmetic coding, larger windows, context modelling, or a full search over short programs) will generally find more structure and produce tighter upper bounds. But no finite family of compressors can be proven to reach K(x) exactly for every input, because doing so would compute the uncomputable function itself. Every real compressor, however good, only ever gives another upper bound.
What is the relationship between Kolmogorov complexity and Shannon entropy?
Shannon entropy measures the average information content of symbols drawn from a known probability distribution — it is a statistical, distribution-level quantity. Kolmogorov complexity measures the information content of one specific, individual string, with no reference to any distribution. For long strings produced i.i.d. from a source, the expected Kolmogorov complexity per symbol converges to the source's entropy rate, linking the two ideas without making them identical.
Compress a bit-string live with a real LZ77-style algorithm and use the compressed length as an honest, computable upper-bound proxy for the provably uncomputable Kolmogorov complexity.
2D · HTML5 Canvas 2D · 60 FPS target · runs fully client-side, no install