Kolmogorov Complexity ($K$) is a way of measuring how complex an object is. For string objects, it is formally defined as the length of the shortest program that generates the string.
For e.g., consider two strings $s:=101010101010$ and $t:=001110101110$. It’s trivial to see how $s$ is less complex, and $K$ helps quantify this. The shortest (Python-style) programs generating these would be print("10"*6) and print("001110101110") respectively, making $K(s) = 13$ and $K(t) = 21$.
However, K is sensitive to the programming language being used. Consider the string $q:=101010…(157923027411234\ \text{times})$, which is generated as print("10"*157923027411234). This makes $K(q) = 27$ and $K(t) < K(q)$. Intuitively though, $q$ is less complex than $t$. This ambiguity is resolved if we consider a language where all numbers are assigned unique symbols, allowing us to generate $q$ as print("10"*φ) and we have $K(q) < K(t)$.
The invariance theorem
Notably, such differences in $K$ measured across various languages cannot be arbitrarily large. This is the invariance theorem:
If $K_1$ and $K_2$ are the complexity functions relative to Turing complete description languages $L_1$ and $L_2$, then there is a constant $c$ – which depends only on the languages $L_1$ and $L_2$ chosen – such that $$\forall s: | K_1(s) − K_2(s) | \leq c.$$
The proof is quite straightforward: consider language $L_1$ where string $s$ is generated by the shortest program $P_1$. Then we can construct a program in language $L_2$ to generate $s$ by writing an interpreter of $L_1$ in $L_2$, and using it to run $P_1$. Since this may not be the most efficient program in $L_2$, we have: $K_2(s) \leq K_1(s) + c$ where $c$ is the length of the interpreter and depends only on the choice of $L_1$ and $L_2$.
Uncomputability
While $K$ is an ideal and a seemingly unambiguous notion—there exists an objectively supreme procedure to produce some object—it is also an uncomputable function, i.e., a terminating algorithm that outputs $K(s)$ for any $s$ cannot be written. The proof by contradiction goes as:
Assume $K$ is computable. Then there exists a program $P$ of length $M$ which outputs $K(s)$ for any $s$. We can now construct a program $P’$ of length $N$ which iterates over all possible strings and using $P$ as a sub-routine, outputs a string with complexity $M + N + 1$. Since a string with complexity $M + N + 1$ is being generated using $P + P’$ of length $M + N$, we arrive at a contradiction.