Questions: Kolmogorov Complexity

Question 1

A string x of one billion bits is produced by a genuinely fair coin. What is its Kolmogorov complexity K(x) most likely to be?

• A. Very low — there is always a pattern if you look hard enough, so a short program exists
• B. Exactly log₂(1,000,000,000) ≈ 30 bits — you only need to specify the length
• C. Close to one billion bits — a truly random string has no description shorter than itself
• D. Exactly one billion bits — random strings have complexity equal precisely to their length

Answer: (C)

A truly random string has, with overwhelming probability, Kolmogorov complexity close to its length — within a small additive constant for program overhead. This is the definition of incompressibility: the string is its own shortest description. Note that K(x) cannot exactly equal n because the program needs some structure beyond the string itself, but the overhead is constant (not growing with n). Option D says 'exactly,' which is wrong; option C says 'close to,' which is correct.

Question 2

If someone claims an algorithm A computes K(x) exactly for every string x, this would imply the halting problem is solvable.

• T. True
• F. False

Answer: True

Computing K(x) requires finding the shortest program that outputs x. To do this, you must enumerate all programs shorter than |x|, run them, and check which ones halt and output x. Deciding whether an arbitrary program halts is the halting problem — which is undecidable. Therefore, no algorithm can compute K(x) for all x. Any claimed algorithm for K would provide a subroutine to decide halting, contradicting its undecidability.

Question 3

The Kolmogorov complexity of a string depends on which universal Turing machine you use as the reference, so it cannot be an objective property of the string.

• T. True
• F. False

Answer: False

The invariance theorem shows that for any two universal Turing machines U and V, |K_U(x) − K_V(x)| ≤ c_UV, where c_UV is a constant depending only on the two machines, not on x. For long strings, this additive constant is negligible. Kolmogorov complexity is therefore machine-independent up to a fixed offset — an objective property of the string in the asymptotic sense, analogous to how the choice of programming language doesn't affect the fundamental limits of what can be computed.

Question 4

A string x of length n is called 'Kolmogorov random.' Which of the following is NOT implied by this characterization?

• A. No program significantly shorter than x can output x
• B. x was generated by a physically random process such as radioactive decay
• C. x has high algorithmic information content
• D. x cannot be significantly compressed by any lossless compression algorithm

Answer: (B)

Kolmogorov randomness is a property of the string itself, not of the process that generated it. A string can be Kolmogorov random even if generated deterministically; conversely, a 'random' process might output a simple string (like all zeros) with very low complexity. Options A, C, and D are all directly implied by incompressibility. Option B confuses algorithmic randomness (a property of strings) with probabilistic randomness (a property of generating processes).

Question 5

Explain the paradox that 'most strings are Kolmogorov random yet you cannot exhibit a specific one,' and what this implies about K as a practical tool.

Model answer: Most strings of length n are incompressible because there are 2^n strings but only 2^(n-1) programs of length less than n — by counting, at least half of all strings cannot be compressed at all. Yet any specific string you point to has just been given a short description (the specification itself), so the act of naming it gives it low complexity. This means Kolmogorov complexity is non-constructive: you can prove random strings exist in abundance without being able to identify any particular one. As a practical tool, K is uncomputable and useless as a compression algorithm. Its power is as a proof technique — the incompressibility method assumes a compressible representation exists, derives a contradiction, and thereby proves the compression is impossible, without ever computing K directly.

The paradox is a consequence of uncomputability: identifying a random string would give it a short description (via the identification), contradicting its randomness. The incompressibility method exploits this non-constructively — it is one of the most elegant proof techniques in theoretical computer science, yielding clean lower bounds in combinatorics, data structures, and communication complexity.