Kolmogorov complexity
Inequalities

We omit additive factors of O (1) {\displaystyle O(1)}. This section is based on.

Theorem. C (x) ≤ K (x) + 2 log 2 C (x) {\displaystyle C(x)\leq K(x)+2\log _{2}C(x)}

Proof. Take any program for the universal Turing machine used to define plain complexity, and convert it to a prefix-free program by first coding the length of the program in binary, then convert the length to prefix-free coding. For example, suppose the program has length 9, then we can convert it as follows: 9 ↦ 1001 ↦ 11 − 00 − 00 − 11 − 01 {\displaystyle 9\mapsto 1001\mapsto 11-00-00-11-\color {red}{01}} where we double each digit, then add a termination code. The prefix-free universal Turing machine can then read in any program for the other machine as follows: {\displaystyle } The first part programs the machine to simulate the other machine, and is a constant overhead O (1) {\displaystyle O(1)}. The second part has length ≤ 2 log 2 C (x) + 3 {\displaystyle \leq 2\log _{2}C(x)+3}. The third part has length C (x) {\displaystyle C(x)}.

Theorem: There exists c {\displaystyle c} such that ∀ x, C (x) ≤ | x | + c {\displaystyle \forall x,C(x)\leq |x|+c}. More succinctly, C (x) ≤ | x | {\displaystyle C(x)\leq |x|}. Similarly, K (x) ≤ | x | + 2 log 2 | x | {\displaystyle K(x)\leq |x|+2\log _{2}|x|}, and K (x | | x |) ≤ | x | {\displaystyle K(x||x|)\leq |x|}.

Proof. For the plain complexity, just write a program that simply copies the input to the output. For the prefix-free complexity, we need to first describe the length of the string, before writing out the string itself.

Theorem. (extra information bounds, subadditivity)

Note that there is no way to compare K (x y) {\displaystyle K(xy)} and K (x | y) {\displaystyle K(x|y)} or K (x) {\displaystyle K(x)} or K (y | x) {\displaystyle K(y|x)} or K (y) {\displaystyle K(y)}. There are strings such that the whole string x y {\displaystyle xy} is easy to describe, but its substrings are very hard to describe.

Theorem. (symmetry of information) K (x, y) = K (x | y, K (y)) + K (y) = K (y, x) {\displaystyle K(x,y)=K(x|y,K(y))+K(y)=K(y,x)}.

Proof. One side is simple. For the other side with K (x, y) ≥ K (x | y, K (y)) + K (y) {\displaystyle K(x,y)\geq K(x|y,K(y))+K(y)}, we need to use a counting argument (page 38).

Theorem. (information non-increase) For any computable function f {\displaystyle f}, we have K (f (x)) ≤ K (x) + K (f) {\displaystyle K(f(x))\leq K(x)+K(f)}.

Proof. Program the Turing machine to read two subsequent programs, one describing the function and one describing the string. Then run both programs on the work tape to produce f (x) {\displaystyle f(x)}, and write it out.
combination:two_responses