Kolmogorov complexity is defined relative to a chosen description language, so why is the measure not arbitrary?

## Why there is a choice to make at all `K(s)` was defined as the length of the shortest program printing `s` - but in which notation? A program is only a program relative to something that runs it. Two reasonable people fixing two different description languages get two different numbers for the same string, and one can rig a language to make any single chosen string cost one bit: build 'print that string' in as the meaning of a one-bit program. Left there, the measure would be a matter of taste. ## The interpreter argument The rescue is that description languages capable of expressing arbitrary computation can simulate one another. Let `U` and `V` be two such languages. 1. Write an interpreter for `V` as a program in `U`. Call its length `c(U,V)`. It is one fixed text, written once. 2. Take any `V`-program `p` that prints `s`. Prefix the interpreter and hand it `p` as data. The result is a `U`-program that prints `s`, of length `|p| + c(U,V)`. 3. Take `p` to be the shortest `V`-program for `s`. Then `K_U(s) <= K_V(s) + c(U,V)`. Run the same construction the other way and you get `K_V(s) <= K_U(s) + c(V,U)`. Put them together with `c` the larger of the two interpreter sizes: ``` |K_U(s) - K_V(s)| <= c for every string s ``` The rigged language is not excluded by this - it still charges one bit for its favourite string - but it must pay the constant everywhere, and the constant was fixed before anybody chose a string. ## What the constant is, and what it is not | Claim about the constant | Status | |---|---| | Depends on the pair of languages | True - it is an interpreter's size | | Depends on the string being measured | False - it is fixed before `s` is chosen | | Additive | True | | A multiplicative factor | False - it never scales with `|s|` | | Can be large in absolute terms | True - kilobytes are entirely possible | Being additive and string-independent is exactly what makes the measure usable, because it means the constant becomes negligible as strings grow. On a gigabyte, a kilobyte-sized interpreter is a rounding error. On a 30-byte string it is the whole answer. ## Which claims survive a change of language Survive: - **Asymptotic statements.** 'Almost all strings of length `n` have complexity within `k` bits of `n`' holds in any language once `n` is large relative to `c`. - **Gross comparisons.** A gigabyte generated from a 200-byte seed has complexity a few hundred bytes plus a constant; no change of language turns that into a gigabyte. - **Impossibility results.** The uncomputability argument is unaffected, since it only needs some fixed language. Do not survive: - **Exact values.** There is no such thing as 'the' complexity of a string to the bit, only its complexity in a stated language. - **Fine comparisons between two similar strings.** If two strings' values differ by less than `c`, a different language may order them the other way. - **Any claim about a very short string.** For a 30-byte string the constant can exceed the string itself, so the number says more about the language than the data. ## How this shows up in a discussion When someone objects that the measure is arbitrary because you can always pick a language that favours your example, the answer is precise: yes for one string, no uniformly - the favour costs a fixed constant paid on every other string, and that constant does not grow with input size. The measure is therefore well-defined **up to an additive constant**, which is the standard phrase and worth saying exactly, because 'up to a constant factor' is a different and false claim. It is also why practitioners state results asymptotically and why nobody quotes a bit-exact complexity for a specific file: the only honest form is a bound, in a named reference language, with the constant acknowledged.