🧮 Kolmogorov Complexity Lab

About this simulation

The Kolmogorov complexity K(x) of a string x is the length of the shortest program that outputs x and halts. It cannot be computed exactly — that would let a program detect its own shortest description, a contradiction related to the halting problem. What we can do is approximate it from above: any compressor that losslessly reproduces x gives an upper bound on K(x), because "decompressor + compressed data" is itself a program that outputs x.

How it works

• Each cube in the grid is one bit of the generated string, laid out left-to-right, top-to-bottom.
• A simple LZ-style scanner looks for repeated substrings it has already seen. Matches are drawn as glowing cyan runs, connected by an arc back to their first occurrence.
• Bits the scanner cannot match anything to stay slate literals — the scanner has to spell them out one by one.
• The compressed-length bar sums the bits needed to encode every literal and every (distance, length) back-reference — a concrete stand-in for an upper bound on K(x).
• Patterned strings compress far below their raw length; a uniformly random string, having no algorithmic shortcut, stays incompressible — its compressed estimate sits at or above its raw length.

Controls

• Source pattern — chooses how the bit string is generated: constant, a repeating motif, the deterministic (but complex-looking) Thue–Morse sequence, prime-indicator bits, or uniform coin flips.
• String length — number of bits rendered in the grid.
• Motif period — length of the repeating unit for the "Repeating motif" pattern.
• Noise injection — randomly flips a percentage of bits after generation, letting you watch compressibility degrade continuously toward incompressible noise.
• 🎲 Regenerate — reseeds the random / noise portions. Drag to rotate, scroll to zoom.

Did you know?

The Thue–Morse sequence looks irregular at a glance, yet it is generated by a tiny rule (start with 0; repeatedly append the bitwise complement of the sequence so far). It is a favorite example in algorithmic information theory of a string with low Kolmogorov complexity that nonetheless fails many statistical randomness tests — a reminder that "looks random" and "is high-complexity" are not the same thing.