Algorithmic probability

In algorithmic information theory, algorithmic probability, also known as Solomonoff probability, is a mathematical method of assigning a prior probability to a given observation. It was invented by Ray Solomonoff in the 1960s.^[2] It is used in inductive inference theory and analyses of algorithms. In his general theory of inductive inference, Solomonoff uses the method together with Bayes' rule to obtain probabilities of prediction for an algorithm's future outputs.^[3]

In the mathematical formalism used, the observations have the form of finite binary strings viewed as outputs of Turing machines, and the universal prior is a probability distribution over the set of finite binary strings calculated from a probability distribution over programs (that is, inputs to a universal Turing machine). The prior is universal in the Turing-computability sense, i.e. no string has zero probability. It is not computable, but it can be approximated.^[4]

Formally, the probability ${\displaystyle P}$ is not a probability and it is not computable. It is only "lower semi-computable" and a "semi-measure". By "semi-measure", it means that ${\displaystyle 0\leq \sum _{x}P(x)<1}$. That is, the "probability" does not actually sum up to one, unlike actual probabilities. This is because some inputs to the Turing machine causes it to never halt, which means the probability mass allocated to those inputs is lost. By "lower semi-computable", it means there is a Turing machine that, given an input string ${\displaystyle x}$, can print out a sequence ${\displaystyle y_{1}<y_{2}<\cdots }$ that converges to ${\displaystyle P(x)}$ from below, but there is no such Turing machine that does the same from above.