Algorithmic Probability and Prefix Complexity in a nutshell
- Algorithmic probability can be measured by feeding random programs into a universal Turing machine.
- An object \(s\) is more probable if it can be generated by short programs.
- Its probability is the sum of the probabilities of all programs that generate it:
\(Pr(s) = \sum_{p; U(p)=s}{2^{-l(p)}}\)
- This only works, however, if these programs are exclusive of each other.
- Considering only programs that have an unambiguous end leads to defining Prefix complexity \(K(s)\).