Editing Algorithmic probability (section)

== Fundamental Theorems ==

=== I. Kolmogorov's Invariance Theorem ===

Kolmogorov's Invariance theorem clarifies that the Kolmogorov Complexity, or ''Minimal Description Length'', of a dataset 
is invariant to the choice of Turing-Complete language used to simulate a Universal Turing Machine:

:<math>\forall x \in \{0,1\}^*, |K_U(x)-K_{U'}(x) | \leq \mathcal{O}(1) 
</math>

where <math>K_U(x) = \min_{p} \{|p|: U(p) = x\}</math>.

=== Interpretation ===

The minimal description <math>p</math> such that <math>U(p) = x</math> serves as a natural representation of the string <math>x</math> relative to the Turing-Complete language <math>U</math>. Moreover, as <math>x</math> can't be compressed further <math>p</math> is an incompressible and hence uncomputable string. This corresponds to a scientists' notion of randomness and clarifies the reason why Kolmogorov Complexity is not computable.

It follows that any piece of data has a necessary and sufficient representation in terms of a random string.

=== 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.

=== II. Levin's Universal Distribution ===

Given that any uniquely-decodable code satisfies the Kraft-McMillan inequality, prefix-free Kolmogorov Complexity allows us to derive the Universal 
Distribution:

:<math>
P(x) = \sum_{U(p) = x} P(U(p) = x) = \sum_{U(p) = x} 2^{-K_U(p)} \leq 1 </math>

where the fact that <math>U</math> may simulate a prefix-free UTM implies that for two distinct descriptions <math>p</math> and <math>p'</math>, <math>p</math> isn't 
a substring of <math>p'</math> and <math>p'</math> isn't a substring of <math>p</math>.

=== Interpretation ===

In a Computable Universe, given a phenomenon with encoding <math>x \in \{0,1\}^*</math> generated by a physical process the probability of that phenomenon is well-defined and equal to the sum over the probabilities of distinct and independent causes. The prefix-free criterion is precisely what guarantees causal independence.

=== Proof ===

This is an immediate consequence of the [[Kraft-McMillan inequality]].

Kraft's inequality states that given a sequence of strings <math>\{x_i\}_{i=1}^n</math> there exists a prefix code with codewords <math>\{\sigma_i\}_{i=1}^n</math> where <math>\forall i, |\sigma_i|=k_i</math> if and only if:

:<math>
\sum_{i=1}^n s^{-k_i} \leq 1	 
</math>

where <math>s</math> is the size of the alphabet <math>S</math>.

Without loss of generality, let's suppose we may order the <math>k_i</math> such that:

:<math>
k_1 \leq k_2 \leq ... \leq k_n	
</math>

Now, there exists a prefix code if and only if at each step <math>j</math> there is at least one codeword to choose that does not contain any of the previous <math>j-1</math> codewords as a prefix. Due to the existence of a codeword at a previous step <math>i<j, s^{k_j-k_i}</math> codewords are forbidden as they contain <math>\sigma_i</math> as a prefix. It follows that in general a prefix code exists if and only if:

:<math>
\forall j \geq 2, s^{k_j} > \sum_{i=1}^{j-1} s^{k_j - k_i}	
</math>

Dividing both sides by <math>s^{k_j}</math>, we find:

:<math>
\sum_{i=1}^n s^{-k_i} \leq 1	 
</math>

QED.