A Computable Measure of Algorithmic Probability by Finite Approximations.
Fernando Soler Toscano, Héctor Zenil · arXiv (Cornell University) · 2015
We study formal properties of a Levin-inspired measure $m$ calculated from the output distribution of small Turing machines. We introduce and justify finite approximations $m_k$ that have already been used in applications as an alternative to lossless compression algorithms for approximating algorithmic (Kolmogorov-Chaitin) complexity. We provide proofs of the relevant properties of both $m$ and $m_k$ and compare them to Levin's Universal Distribution. Finally, we provide error estimations of $m_k$ with respect to $m$.