This appendix represents a formal equivalent of the basic concepts discussed in the article.
Each Turing machine (TM) C (mapping bitstrings to bitstrings, without loss of generality) computes a partial function fC : {0,1}* -> {0,1}*. (fC is undefined where C does not halt).
Compiler theorem. There is a universal TM U with the following property: for every TM C there exists a constant prefix mu_C (a bitstring) such that fC (p)= fU (mu_C p) for all bitstrings p. mu_C is the compiler that compiles programs for C into equivalent programs for U.
Kolmogorov complexity. The Kolmogorov complexity KU(s) of a finite string s is the length of the shortest program p that computes s on a universal Turing machine U and halts, where the set of possible halting programs forms a prefix code (no halting program can be the prefix of another one): KU(s) = minp {| p | : fU (p) = s}, where | p | denotes the length of p. In general, KU(s) is noncomputable.
Invariance theorem. Due to the compiler theorem, KU1(s) = KU2(s) + O(1) for two universal machines U1 and U2. We choose one particular universal machine U and write K(s) = KU(s).