Editing Kolmogorov complexity (section)

===A more formal treatment===
'''Theorem''': If ''K''<sub>1</sub> and ''K''<sub>2</sub> are the complexity functions relative to [[Turing complete]] description languages ''L''<sub>1</sub> and ''L''<sub>2</sub>, then there is a constant ''c''&nbsp;– which depends only on the languages ''L''<sub>1</sub> and ''L''<sub>2</sub> chosen&nbsp;– such that

:∀''s''.  −''c'' ≤ ''K''<sub>1</sub>(''s'') − ''K''<sub>2</sub>(''s'') ≤ ''c''.

'''Proof''': By symmetry, it suffices to prove that there is some constant ''c'' such that for all strings ''s''

:''K''<sub>1</sub>(''s'') ≤ ''K''<sub>2</sub>(''s'') + ''c''.

Now, suppose there is a program in the language ''L''<sub>1</sub> which acts as an [[interpreter (computing)|interpreter]] for ''L''<sub>2</sub>:

 '''function''' InterpretLanguage('''string''' ''p'')

where ''p'' is a program in ''L''<sub>2</sub>. The interpreter is characterized by the following property:

: Running <code>InterpretLanguage</code> on input ''p'' returns the result of running ''p''.

Thus, if '''P''' is a program in ''L''<sub>2</sub> which is a minimal description of ''s'', then <code>InterpretLanguage</code>('''P''') returns the string ''s''. The length of this description of ''s'' is the sum of

# The length of the program <code>InterpretLanguage</code>, which we can take to be the constant ''c''.
# The length of '''P''' which by definition is ''K''<sub>2</sub>(''s'').

This proves the desired upper bound.