Editing Kolmogorov complexity (section)

=== Inequalities ===
We omit additive factors of <math>O(1)</math>. This section is based on.<ref name=":0" />

'''Theorem.''' <math>K(x) \leq C(x) + 2\log_2 C(x) </math>

'''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:<math display="block">9 \mapsto 1001 \mapsto 11-00-00-11-\color{red}{01} </math>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:<math display="block">[\text{code for simulating the other machine}][\text{coded length of the program}][\text{the program}]</math>The first part programs the machine to simulate the other machine, and is a constant overhead <math>O(1)</math>. The second part has length <math>\leq 2 \log_2 C(x) + 3</math>. The third part has length <math>C(x)</math>.

'''Theorem''': There exists <math>c</math> such that <math>\forall x, C(x) \leq |x| + c</math>. More succinctly, <math>C(x) \leq |x|</math>. Similarly, <math>K(x) \leq |x| + 2\log_2 |x|</math>, and <math>K(x | |x|) \leq |x| </math>.{{clarify|reason=This appears to be the first use of conditional complexity notation. Its definition should occur before here. Moreover, notation could better be changed to avoid confusion with string length (maybe, string length is better denoted by '#x').|date=January 2024}}

'''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)'''

* <math>K(x | y) \leq K(x) \leq K(x, y) \leq \max( K(x|y) + K(y), K(y|x) + K(x)) \leq K(x) + K(y) </math>
* <math>K(xy) \leq K(x, y)</math>
Note that there is no way to compare <math>K(xy)</math> and <math>K(x|y)</math> or <math>K(x)</math> or <math>K(y|x)</math> or <math>K(y)</math>. There are strings such that the whole string <math>xy</math> is easy to describe, but its substrings are very hard to describe.

'''Theorem. (symmetry of information)''' <math>K(x, y) = K(x | y, K(y)) + K(y)  = K(y, x)</math>.

'''Proof.''' One side is simple. For the other side with <math>K(x, y) \geq K(x | y, K(y)) + K(y)</math>, we need to use a counting argument (page 38 <ref>{{Cite book |last=Hutter |first=Marcus |title=Universal artificial intelligence: sequential decisions based on algorithmic probability |date=2005 |publisher=Springer |isbn=978-3-540-26877-2 |series=Texts in theoretical computer science |location=Berlin New York}}</ref>).

'''Theorem. (information non-increase)''' For any computable function <math>f</math>, we have <math>K(f(x)) \leq K(x) + K(f)</math>.

'''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 <math>f(x)</math>, and write it out.