computer program P (part 1), and then using the original description D as input to that program (part 2). The total length of this new description D′ is (approximately): |D′ | = |P| + |D| The length of P is a constant that doesn't depend on D. So, there is at most a constant overhead, regardless of the object described. Therefore, the optimal language is universal up to this additive constant. A more formal treatment Theorem: If K1 and K2 are the complexity functions relative to Turing complete description languages L1 and L2, then there is a constant c – which depends only on the languages L1 and L2 chosen – such that ∀s. −c ≤ K1(s) − K2(s) ≤ c. Proof: By symmetry, it suffices to prove that there is some constant c such that for all strings s K1(s) ≤ K2(s) + c. Now, suppose there is a program in the language L1 which acts as an interpreter for L2: function InterpretLanguage(string p) where p is a program in L2. The interpreter is characterized by the following property: Running InterpretLanguage on input p returns the result of running p. Thus, if P is a program in L2 which is a minimal description of s, then InterpretLanguage(P) returns the string s. The length of this description of s is the sum of The length of the program InterpretLanguage, which we can take to be the constant c. The length of P which by definition is K2(s). This proves the desired upper bound. History and context Algorithmic information theory is the area of computer science that studies Kolmogorov complexity and other complexity measures on strings (or other data structures). The concept and theory of Kolmogorov Complexity is based on a crucial theorem first discovered by Ray Solomonoff, who published it in 1960, describing it in "A Preliminary Report on a General Theory of Inductive Inference" as part of his invention of algorithmic probability. He gave a more complete description in his 1964 publications, "A Formal Theory of Inductive Inference," Part 1 and Part 2 in Information and Control. Andrey Kolmogorov later independently published this theorem in Problems Inform. Transmission in 1965. Gregory Chaitin also presents this theorem in J. ACM – Chaitin's paper was submitted October 1966 and revised in December 1968, and cites both Solomonoff's and Kolmogorov's papers. The theorem says that, among algorithms that decode strings from their