Editing Algorithmic probability (section)

=== Proof ===

The following is taken from <ref>Grünwald, P. and Vitany, P. Algorithmic Information Theory. Arxiv. 2008.</ref>

From the theory of compilers, it is known that for any two Turing-Complete languages <math>U_1</math> and <math>U_2</math>, there exists a compiler <math>\Lambda_1</math> expressed in 
<math>U_1</math> that translates programs expressed in <math>U_2</math> into functionally-equivalent programs expressed in <math>U_1</math>.

It follows that if we let <math>p</math> be the shortest program that prints a given string <math>x</math> then:

:<math>
K_{U_1}(x) \leq |\Lambda_1| + |p| \leq K_{U_2}(x) + \mathcal{O}(1)	
</math>

where <math>|\Lambda_1| = \mathcal{O}(1)</math>, and by symmetry we obtain the opposite inequality.