Editing Algorithmic probability (section)

{{Short description|Mathematical method of assigning a prior probability to a given observation}}
[[File:From observer states to physics via algorithmic probability.png|thumb|From observer states to physics via algorithmic probability. A colorful illustration of Observation 5.4 shows the computational ontological model's possible histories, represented as a tree graph. The vertices correspond to the random variable <math>\omega_t</math> (the computational state at time <math>t</math>), with valid states (black) forming a growing sequence of bit strings, while invalid states are shown in gray. Alice and Bob, observing an approaching meteorite, are part of the computational process, represented by <math>f_A(\omega_t')</math> and <math>f_B(\omega_t')</math>, respectively. Their shared emergent reality transitions probabilistically: with 99% likelihood, the meteorite hits Bob3rd, and with 1%, it misses. Postulates 3.2 imply this outcome is irrelevant for Bob1st, whose state transitions elsewhere, as <math>f_B</math> generates a semimeasure, not a measure. The fate of Bob1st lies beyond the scope of Postulates 3.2, awaiting Postulates 3.1.<ref>Markus Müller."Law without law: from observer states to physics via algorithmic information theory." Quantum 4 (2020): 301.https://quantum-journal.org/papers/q-2020-07-20-301/pdf/</ref>]]

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.<ref>Solomonoff, R., "[http://world.std.com/~rjs/z138.pdf A Preliminary Report on a General Theory of Inductive Inference]", Report V-131, Zator Co., Cambridge, Ma. (Nov. 1960 revision of the Feb. 4, 1960 report).</ref> 
It is used in inductive inference theory and analyses of algorithms. In his [[Solomonoff's theory of inductive inference|general theory of inductive inference]], Solomonoff uses the method together with [[Bayes' rule]] to obtain probabilities of prediction for an algorithm's future outputs.<ref>Li, M. and Vitanyi, P., ''An Introduction to Kolmogorov Complexity and Its Applications'', 3rd Edition, Springer Science and Business Media, N.Y., 2008</ref>

In the mathematical formalism used, the observations have the form of finite binary strings viewed as outputs of [[Turing machine]]s, 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.<ref>Hutter, M., Legg, S., and Vitanyi, P., [http://www.scholarpedia.org/article/Algorithmic_probability "Algorithmic Probability"], Scholarpedia, 2(8):2572, 2007.</ref>

Formally, the probability <math>P</math> 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 <math>0 \le \sum_x P(x) < 1</math>. 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 <math>x</math>, can print out a sequence <math>y_1 < y_2 < \cdots</math> that converges to <math>P(x)</math> from below, but there is no such Turing machine that does the same from above.