next up previous
Next: Dominant and Universal (Semi)Measures Up: HIERARCHIES OF GENERALIZED KOLMOGOROV Previous: Relation to Conditional Complexity

Measures and Probability Distributions

We will now show how the Kolmogorov complexity hierarchy introduced above translates into an algorithmic prior hierarchy.

Suppose $x$ represents the history of our universe up until now. What is its most likely continuation $y in B^{sharp}$? Bayes' theorem yields

P(xy \mid x)
= \frac{P(x \mid xy) P(xy)} {\sum_{z \in B^{\sharp}} P(xz)}
= \frac{P(xy)} {N(x)}
\propto P(xy)
\end{displaymath} (13)

where $P(z^2 mid z^1)$ is the probability of $z^2$, given knowledge of $z^1$, and
N(x) = \sum_{z \in B^{\sharp}} P(xz)
\end{displaymath} (14)

is a normalizing factor. The most likely continuation $y$ is determined by $P(xy)$, the prior probability of $xy$. Now what are the formally describable ways of assigning prior probabilities to computable universes? In what follows we will first consider traditional describable semimeasures on $B^*$, then nontraditional probability distributions on $B^{sharp}$.


Juergen Schmidhuber 2003-02-13