Editing Kolmogorov complexity (section)

== Universal probability ==
Fix a universal Turing machine <math>U</math>, the same one used to define the (prefix-free) Kolmogorov complexity. Define the (prefix-free) universal probability of a string <math>x</math> to be<math display="block">P(x) = \sum_{U(p) = x} 2^{-l(p)}</math>In other words, it is the probability that, given a uniformly random binary stream as input, the universal Turing machine would halt after reading a certain prefix of the stream, and output <math>x</math>.

Note. <math>U(p) = x</math> does not mean that the input stream is <math>p000\cdots</math>, but that the universal Turing machine would halt at some point after reading the initial segment <math>p</math>, without reading any further input, and that, when it halts, its has written <math>x</math> to the output tape.

'''Theorem.''' (Theorem 14.11.1<ref name=":1" />) <math>\log \frac{1}{P(x)} = K(x) + O(1)</math>