Why can no program compute the Kolmogorov complexity of an arbitrary input string?

seniorshould knowfreq 30%

answer

assume it exists, then use it
search for a string it certifies
the searcher is far shorter than N
only finitely many strings sit under N
approachable from above, never certified

basics

~20 s

Because such a function lets you write a short program that hunts down and prints the first string it certifies as needing a long description, describing that string in far fewer bits than the certificate claims. The contradiction rules the function out.

solid answer

~40 s

Suppose some program COMPLEXITY(s) always returns the true shortest-description length of s. Pick a large number N and write a second program: walk strings in length order, call COMPLEXITY on each, and print the first one whose value exceeds N. Such a string exists, because only finitely many strings have complexity at most N. But that searcher is short - a fixed body plus the digits of N, roughly log2(N) bits - and it prints a string it just certified as needing more than N bits to describe. The searcher is a description of that string, so the certificate contradicts itself. No total COMPLEXITY can exist. What survives is one-sided: you can keep lowering your best upper bound as shorter descriptions turn up, but never certify that you have reached the minimum.

Suppose some program `COMPLEXITY(s)` always returns the true shortest-description length of `s`. Pick a large number `N` and write a second program: walk strings in length order, call `COMPLEXITY` on each, and print the first one whose value exceeds `N`. Such a string exists, because only finitely many strings have complexity at most `N`. But that searcher is short - a fixed body plus the digits of `N`, roughly `log2(N)` bits - and it prints a string it just certified as needing more than `N` bits to describe. The searcher *is* a description of that string, so the certificate contradicts itself. No total `COMPLEXITY` can exist. What survives is one-sided: you can keep lowering your best upper bound as shorter descriptions turn up, but never certify that you have reached the minimum.

code

pseudocode · 6 lines

pseudocode

# assume COMPLEXITY(s) returns the true shortest-description length
N = 1000000                                  # a literal costing about 20 bits
for each s in strings ordered by length, then alphabetically:
    if COMPLEXITY(s) > N:
        emit(s)
        halt

go deeper

for a junior

Take away the headline: no program can tell you a file's true shortest description length. Tools report what they achieved, which is an estimate from one side only.

for a middle

Be able to sketch the searcher: hunt for the first string certified as needing more than N bits, notice the hunter is much shorter than N, and see that it has described that string itself.

for a senior

Apply it: reject any dashboard field claiming true information content, and design around the untestable property using provenance and construction rules rather than a measurement.

for a principal

The lesson generalises past this measure. When a property you want to govern is not checkable, the decision is which substitute evidence your organisation will accept and what a passing check is contractually allowed to mean.

The claim, stated carefully

There is no program that takes an arbitrary finite string and returns its Kolmogorov complexity - the length of the shortest program printing it. This is not a statement about today's algorithms being slow, or about very long inputs being impractical. It is a statement that the function itself cannot be computed, for inputs of any size, by any procedure whatsoever.

The searching program that breaks the assumption

Assume the opposite and build the counterexample. Suppose COMPLEXITY(s) exists, always halts, and always returns the exact value. Now write this:

Hard-code a large number N.
Enumerate all strings in order of length, and alphabetically within a length.
For each string s, call COMPLEXITY(s).
The first time the answer exceeds N, print s and halt.

Three observations finish the argument, and each needs checking:

The search terminates. There are fewer than 2^(N+1) programs of length at most N bits, so at most that many strings have complexity at most N. Strings are infinite in number, so the enumeration must eventually reach one whose complexity exceeds N, and the guard fires there.
The searcher is short. Its text is a fixed body - the enumerator and the call - plus a literal for N, which takes about log2(N) bits to write down. For any large N, constant + log2(N) is far below N.
The searcher describes its own output. It takes no input and prints exactly one string, so it is a program that outputs that string. Therefore that string's complexity is at most the searcher's length, which is less than N.

And the searcher chose that string precisely because its complexity exceeded N. Both statements cannot hold, so the assumption that COMPLEXITY exists is false. The whole force of the argument sits in self-reference: the measuring device gets used to build the object it is measuring.

What you can still compute

The result kills exact computation, not every form of knowledge. Consider running all programs of length at most n simultaneously, a few steps each in rotation, and watching for one that prints your string:

Whenever one of them succeeds, you learn a real upper bound: a description of that length exists.
The bound never stops improving in principle; run longer and a shorter program may still finish.
You never learn when to stop. A candidate still running may print your string in a million more steps or never print anything, and nothing in the procedure distinguishes those two cases.

So the measure is approachable from above only: a sequence of decreasing bounds with no certificate at the end. This is exactly the shape of the practical situation in the previous section - every coder you run is a crude version of that search, and a better coder is a lower bound on nothing.

Question about a string	Answerable by a program?
Is there a description of at most `n` bits?	Yes if one exists and you wait long enough; never a definitive no
What is the exact shortest length?	No, for any input
Is this string incompressible?	No
Does this particular program print it?	Not in general, since the program may not halt

Why an engineer should care

There is no complexity meter, and there never will be one. Any tool reporting 'the true information content' of a payload is reporting what one coder achieved, under a name it has not earned.
Untestable properties need a different kind of evidence. When the property you want cannot be checked, you substitute provenance, construction rules and invariants - you document how the artifact was made rather than measuring the artifact.
One-sided measures are still useful if you respect the side. A ratio that proves a short description exists is real evidence. The same ratio read backwards, as proof that none exists, is the error this result guarantees you cannot fix with a better tool.
Budget your scepticism. Claims of the form 'this data is at its minimum size' are unfalsifiable in the strong sense; the productive version is 'no coder we tried beat this', which is an engineering statement with a date on it.

The interview register here is the idea of the argument, not a formal write-up: the paradoxical searcher, why it terminates, why it is short, and the one-sided approximation left standing.

## The claim, stated carefully There is no program that takes an arbitrary finite string and returns its Kolmogorov complexity - the length of the shortest program printing it. This is not a statement about today's algorithms being slow, or about very long inputs being impractical. It is a statement that the function itself cannot be computed, for inputs of any size, by any procedure whatsoever. ## The searching program that breaks the assumption Assume the opposite and build the counterexample. Suppose `COMPLEXITY(s)` exists, always halts, and always returns the exact value. Now write this: 1. Hard-code a large number `N`. 2. Enumerate all strings in order of length, and alphabetically within a length. 3. For each string `s`, call `COMPLEXITY(s)`. 4. The first time the answer exceeds `N`, print `s` and halt. Three observations finish the argument, and each needs checking: - **The search terminates.** There are fewer than `2^(N+1)` programs of length at most `N` bits, so at most that many strings have complexity at most `N`. Strings are infinite in number, so the enumeration must eventually reach one whose complexity exceeds `N`, and the guard fires there. - **The searcher is short.** Its text is a fixed body - the enumerator and the call - plus a literal for `N`, which takes about `log2(N)` bits to write down. For any large `N`, `constant + log2(N)` is far below `N`. - **The searcher describes its own output.** It takes no input and prints exactly one string, so it is a program that outputs that string. Therefore that string's complexity is at most the searcher's length, which is less than `N`. And the searcher chose that string precisely because its complexity exceeded `N`. Both statements cannot hold, so the assumption that `COMPLEXITY` exists is false. The whole force of the argument sits in self-reference: the measuring device gets used to build the object it is measuring. ## What you can still compute The result kills exact computation, not every form of knowledge. Consider running all programs of length at most `n` simultaneously, a few steps each in rotation, and watching for one that prints your string: - Whenever one of them succeeds, you learn a real **upper bound**: a description of that length exists. - The bound never stops improving in principle; run longer and a shorter program may still finish. - You never learn when to stop. A candidate still running may print your string in a million more steps or never print anything, and nothing in the procedure distinguishes those two cases. So the measure is approachable **from above only**: a sequence of decreasing bounds with no certificate at the end. This is exactly the shape of the practical situation in the previous section - every coder you run is a crude version of that search, and a better coder is a lower bound on nothing. | Question about a string | Answerable by a program? | |---|---| | Is there a description of at most `n` bits? | Yes if one exists and you wait long enough; never a definitive no | | What is the exact shortest length? | No, for any input | | Is this string incompressible? | No | | Does this particular program print it? | Not in general, since the program may not halt | ## Why an engineer should care - **There is no complexity meter, and there never will be one.** Any tool reporting 'the true information content' of a payload is reporting what one coder achieved, under a name it has not earned. - **Untestable properties need a different kind of evidence.** When the property you want cannot be checked, you substitute provenance, construction rules and invariants - you document how the artifact was made rather than measuring the artifact. - **One-sided measures are still useful if you respect the side.** A ratio that proves a short description exists is real evidence. The same ratio read backwards, as proof that none exists, is the error this result guarantees you cannot fix with a better tool. - **Budget your scepticism.** Claims of the form 'this data is at its minimum size' are unfalsifiable in the strong sense; the productive version is 'no coder we tried beat this', which is an engineering statement with a date on it. The interview register here is the idea of the argument, not a formal write-up: the paradoxical searcher, why it terminates, why it is short, and the one-sided approximation left standing.

If you only care about short inputs, can you brute-force the exact value by trying every shorter program?
No. You can enumerate the candidate programs easily enough, but you must decide, for each one still running, whether it will ever print your string. Nothing lets you distinguish a slow candidate from one that never finishes, so the brute force has no stopping point even for a ten-byte input.
What is left of the measure if it cannot be computed?
Two things stay useful. Upper bounds: any decoder plus payload certifies one. And population-level results: statements that almost all strings of a given length need close to that many bits hold without ever naming a witness. Both are used to refute claims rather than to score files.
Does the argument depend on the number N being large?
Yes, and that is the crux. The searcher costs a fixed body plus about log2(N) bits, so the contradiction needs N large enough that this total falls below N. Any sufficiently large N works, which is all the argument requires.

Consider the phrase 'the smallest number not describable in fewer than twenty words'. It has fourteen words and just described that number. A complexity oracle lets you turn that word game into a running program.

saying these in an interview costs you the question

Says the measure is merely too slow to compute in practice
Claims brute force settles it for short strings
Thinks uncomputability means no evidence about complexity exists
Believes a good coder gives a lower bound on complexity
Reports a tool's output as a string's true information content

Why can no program compute the Kolmogorov complexity of an arbitrary input string?

§ answer

basics

solid answer

code

§ go deeper

▾level notes4 levels

▾deep dive~4 min

The claim, stated carefully

The searching program that breaks the assumption

What you can still compute

Why an engineer should care

▾common follow-ups3 questions

▾analogy~20 s

▾red flags5 flags

The claim, stated carefully

The searching program that breaks the assumption

What you can still compute

Why an engineer should care

answer

go deeper