Introduction

What does it mean for a string of bits to be truly random? Not "produced by a random process" but intrinsically patternless — with no shortcut, no formula, no description shorter than the string itself?

The answer came independently from three researchers in the 1960s: Andrei Kolmogorov (1965), Ray Solomonoff (1964), and Gregory Chaitin (1966). Their idea was elegant: the Kolmogorov complexity K(s) of a string s is the length, in bits, of the shortest computer program that outputs s and then halts.

A string like "AAAAAAAAAAAAAAAA" (16 A's) has a short description: "Print A sixteen times." That's a tiny program. But a string like "10110100011010110110" — if it truly has no pattern — cannot be described any more briefly than by just writing it out. Its complexity equals its length.

This one idea unifies data compression (can we compress a file? only if its complexity is less than its size), randomness (a string is random when it can't be compressed), and machine learning (simple models that generalize well correspond to short descriptions of the data). Kolmogorov complexity is the foundation of algorithmic information theory, and it reveals one of the deepest limits of computation: the complexity of most strings is uncomputable.

Try It: Upper Bounds in Action

The demo below lets you enter any string and watch a simple run-length encoder compress it. The compressed length gives an upper bound on the Kolmogorov complexity — proof that a short program (the decompressor + the compressed data) can reproduce the original.

<p class="hint">Enter any string and see how a run-length encoder compresses it. The compressed length is an <b>upper bound</b> on Kolmogorov complexity — it proves a short program can reproduce the string. Try structured vs random strings.</p>
<div class="controls">
  <input id="strInput" type="text" maxlength="120" placeholder="e.g. ABABABABABABABABAB" autocomplete="off" spellcheck="false" />
  <button id="compressBtn" type="button">Compress</button>
</div>
<div class="presets">
  <span class="label">Presets:</span>
  <button class="preset" data-val="AAAAAAAAAAAAAAAAAAAAAAAAA">25×A</button>
  <button class="preset" data-val="ABABABABABABABABABABABABAB">ABAB×12</button>
  <button class="preset" data-val="AAABBBCCCDDDEEEFFFGGGHHH">ABC runs</button>
  <button class="preset" data-val="BDKFQMXZWRJVNTHPLCSGYBEA">random-like</button>
</div>
<div id="result" class="result hidden">
  <div class="bar-row">
    <span class="bar-label">Original</span>
    <div class="bar-wrap"><div id="origBar" class="bar orig"></div></div>
    <span class="bar-num" id="origLen">0</span>
  </div>
  <div class="bar-row">
    <span class="bar-label">Compressed</span>
    <div class="bar-wrap"><div id="compBar" class="bar comp"></div></div>
    <span class="bar-num" id="compLen">0</span>
  </div>
  <div class="detail" id="detail"></div>
  <div class="verdict" id="verdict"></div>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .8rem; line-height: 1.5; }
.controls { display: flex; gap: .5rem; margin-bottom: .5rem; }
#strInput { flex: 1; font: 14px ui-monospace, monospace; padding: .4rem .6rem;
            border: 1px solid #adb1b8; border-radius: 8px; outline: none; }
#strInput:focus { border-color: #1d3557; }
button { font: 600 13px system-ui, sans-serif; padding: .4rem .8rem;
         border: 1px solid #1d3557; background: #1d3557; color: #fff;
         border-radius: 8px; cursor: pointer; white-space: nowrap; }
button:hover { background: #162a45; }
.presets { display: flex; flex-wrap: wrap; gap: .4rem; align-items: center; margin-bottom: .9rem; }
.label { font-size: .8rem; color: #666; }
.preset { font: 600 11px ui-monospace, monospace; padding: .28rem .55rem;
          background: #e8eef3; color: #1d3557; border: 1px solid #cdd9e3;
          border-radius: 6px; cursor: pointer; }
.preset:hover { background: #d0dce8; }
.result { margin-top: .4rem; }
.result.hidden { display: none; }
.bar-row { display: flex; align-items: center; gap: .5rem; margin-bottom: .45rem; }
.bar-label { width: 88px; font-size: .82rem; color: #555; flex-shrink: 0; }
.bar-wrap { flex: 1; background: #e8eef3; border-radius: 5px; overflow: hidden; height: 18px; }
.bar { height: 18px; border-radius: 5px; transition: width .4s ease; min-width: 4px; }
.bar.orig { background: #1d3557; }
.bar.comp { background: #2a9d8f; }
.bar-num { width: 36px; font: 700 13px ui-monospace, monospace; color: #333; text-align: right; flex-shrink: 0; }
.detail { font: 13px ui-monospace, monospace; background: #f4f6f8; border: 1px solid #dde2e8;
          border-radius: 8px; padding: .5rem .7rem; margin-top: .5rem; white-space: pre-wrap; word-break: break-all; color: #333; }
.verdict { margin-top: .6rem; font-size: .93rem; font-weight: 600; padding: .45rem .7rem;
           border-radius: 8px; line-height: 1.4; }
.verdict.low  { background: #d4edda; color: #155724; }
.verdict.med  { background: #fff3cd; color: #856404; }
.verdict.high { background: #f8d7da; color: #721c24; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Run-length encoding: compress runs of identical characters.
// Output format: count (if >1) then char. Digit chars are escaped with ’~’
// so the decompressor can distinguish them from run-count digits.
// E.g. "AAABBC" -> "3A2BC", "111" -> "3~1", "a1b" -> "a~1b"
// This gives an UPPER BOUND on Kolmogorov complexity K(s):
//   K(s) <= |compressed| + |decompressor constant|
// Highly structured strings compress a lot; truly random strings expand (because digit escaping adds overhead), proving no short description exists.

function rleCompress(s) {
  if (!s.length) return '';
  let out = '';
  let i = 0;
  while (i < s.length) {
    let j = i;
    while (j < s.length && s[j] === s[i]) j++;
    const run = j - i;
    const ch = s[i];
    const isDigit = ch >= '0' && ch <= '9';
    const encoded = isDigit ? ('~' + ch) : ch;
    out += (run > 1 ? run : '') + encoded;
    i = j;
  }
  return out;
}

function rleDecompress(c) {
  let out = '';
  let i = 0;
  while (i < c.length) {
    let numStr = '';
    while (i < c.length && c[i] >= '0' && c[i] <= '9') { numStr += c[i]; i++; }
    if (i >= c.length) break;
    let ch;
    if (c[i] === '~') { i++; ch = c[i]; i++; }
    else { ch = c[i]; i++; }
    const count = numStr ? parseInt(numStr) : 1;
    out += ch.repeat(count);
  }
  return out;
}

function compress() {
  const raw = document.getElementById('strInput').value.trim();
  if (!raw) return;
  const comp = rleCompress(raw);
  const origLen = raw.length;
  const compLen = comp.length;
  const ratio = compLen / origLen;

  document.getElementById('result').classList.remove('hidden');
  document.getElementById('origLen').textContent = origLen;
  document.getElementById('compLen').textContent = compLen;

  const pct = Math.min(150, Math.round(ratio * 100));
  document.getElementById('origBar').style.width = '100%';
  document.getElementById('compBar').style.width = Math.min(100, pct) + '%';

  const saved = origLen - compLen;
  const savedPct = Math.round((1 - ratio) * 100);
  document.getElementById('detail').textContent =
    fmt(`Original  : %raw%
RLE output: %comp%
%v%`, { raw: raw, comp: comp, v: saved > 0
      ? fmt(`Saved     : %saved% chars (%savedPct%% reduction)`, { saved: saved, savedPct: savedPct })
      : fmt(`Expanded  : %expanded% chars (no runs found; digit escaping adds overhead)`, { expanded: -saved }) });

  const vEl = document.getElementById('verdict');
  let cls, msg;
  if (ratio <= 0.5) {
    cls = 'low';
    msg = fmt(`K(s) ≤ %compLen% chars — highly compressible. This string has a short description: its true complexity is much less than its length.`, { compLen: compLen });
  } else if (ratio < 1.0) {
    cls = 'med';
    msg = fmt(`K(s) ≤ %compLen% chars — partially compressible. Some structure exists, but the string resists full compression.`, { compLen: compLen });
  } else {
    cls = 'high';
    msg = fmt(`K(s) ≤ %origLen% chars (original length) — no compression found. This string resists run-length encoding: its complexity is at least as large as its length, a hallmark of randomness.`, { origLen: origLen });
  }
  vEl.className = 'verdict ' + cls;
  vEl.textContent = msg;

  // Verify roundtrip correctness
  const recovered = rleDecompress(comp);
  console.assert(recovered === raw, `RLE roundtrip failed!`);
  console.log(`Input:`, raw, '| Compressed:', comp, '| Ratio:', ratio.toFixed(3));
}

document.getElementById('compressBtn').addEventListener('click', compress);
document.getElementById('strInput').addEventListener('keydown', function(e) { if (e.key === 'Enter') compress(); });
document.querySelectorAll('.preset').forEach(function(btn) {
  btn.addEventListener('click', function() {
    document.getElementById('strInput').value = btn.dataset.val;
    compress();
  });
});

// Run on a default string immediately
document.getElementById('strInput').value = 'ABABABABABABABABABABABABAB';
compress();
Result
Console

Notice what happens. A highly structured string like ABABABABAB compresses dramatically — its true complexity is low. A string of digits of π compresses a bit, because there's a short program that generates π. A genuinely random-looking string resists compression entirely: the best upper bound we can find is nearly equal to the string's own length.

The key insight: we can only ever upper-bound K(s). Any compression algorithm that produces a shorter description proves K(s) is at most that length. But proving K(s) is exactly some value — proving no shorter program exists — would require searching all programs, which is uncomputable.

The Real Complexity

Kolmogorov complexity has a precise, beautiful definition — and a devastating consequence: it is uncomputable, proven impossible (not merely hard) in the same sense as the halting problem.

Why it's uncomputable. Suppose a function K(s) existed that computed the exact Kolmogorov complexity of any string s. We could use it to find, for each n, the shortest string with complexity ≥ n — call it the "most random" n-bit string. But a program that prints that string would be short (it just calls K, searches, and prints), creating a contradiction: a short program outputs a string with high complexity. This is Berry's paradox formalized, and it proves K is incomputable.

What we can say:

  • Upper bounds are computable: any compression algorithm gives an upper bound. Run gzip on a string of length n: if the output is k bits, then K(s) ≤ k + |gzip|.
  • Most strings are incompressible: for any length n, at most half of n-bit strings can be compressed by even one bit. So most strings are nearly as complex as their own length — randomness is the rule, not the exception.
  • K is invariant up to a constant: the choice of programming language doesn't matter beyond a fixed constant. Kolmogorov and Chaitin proved that switching from one universal computer to another changes K(s) by at most a constant independent of s (the invariance theorem).
  • Logical depth (Bennett, 1988) extends the idea: a string is "deep" if it takes a long computation to produce from its shortest description — capturing the intuition that complex organized structures (like life) require both low randomness and long computation to generate.

The incomputability of K doesn't make it useless — on the contrary, it is the gold standard against which every real compressor is measured.

Where It Matters

Though K itself is uncomputable, the concept drives real-world science and engineering in surprising ways:

  • Data compression: every compressor (gzip, JPEG, MP3) is an approximation to K. The theoretical limit of lossless compression for any file is its Kolmogorov complexity — Shannon entropy is a probabilistic average, but K is the individual-string floor.
  • Minimum Description Length (MDL): in statistics and machine learning, the MDL principle (Rissanen, 1978) says the best model for data is the one that most compresses it. This is Kolmogorov complexity in practice: short models that compress data well are preferred over complex ones that overfit — directly connecting K to Occam's razor.
  • Randomness testing: a string passes randomness tests if and only if it is incompressible (Martin-Löf, 1966). This unified dozens of ad-hoc statistical tests under one clean definition. The same idea appears in PAC learning: random data is the hardest to learn from, because there is no pattern.
  • Scientific explanation: Solomonoff's universal prior says the simplest theory consistent with observations should be favored — literally the shortest program that generates all known data. This is a formal version of the scientific method.
  • Normalized compression distance (NCD): you can measure how "similar" two objects are by compressing them together. NCD(x, y) = (K(xy) - min(K(x), K(y))) / max(K(x), K(y)). In practice, use a real compressor in place of K; the result clusters languages, music genres, and DNA sequences correctly.

Kolmogorov complexity is the invisible ruler behind every algorithm that asks: is this data simpler than it looks?

Conclusion

Kolmogorov complexity answers the oldest question in information theory: how much information does this string really contain? The answer is the length of the shortest program that produces it — a number that is precise, universal, and forever out of reach.

You can compress a file and prove K is at most some value. You can show that a random string resists every compressor. But you can never certify that you've found the absolute shortest description, because doing so would solve the halting problem.

That incomputability is not a defect — it is the signature of a concept that sits at the very bottom of mathematics. Every time a compressor shrinks a file, every time a machine learning model generalizes from few examples, every time a scientist prefers the simpler of two theories: Kolmogorov's ghost is measuring the description length.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/kolmogorov-complexity/Content licensed under CC BY-NC 4.0.