Projects
Solomonoff Induction and Algorithmic Randomness
For sequential prediction tasks, Solomonoff’s celebrated result guarantees the inductive success of the “simplicity” prior by showing that the predictive probabilities induced by any optimal c.e. semimeasure converge to the posterior of the true probability almost surely. Hutter and Muchnik have shown that there exists an optimal c.e. semimeasure for which one can construct a Martin-Löf sequence along which this optimal semimeasure fails to converge to the uniform measure. Since the study of algorithmic randomness can be used to characterize “almost-sure” convergence theorems, one can ask whether stronger notions of randomness suffice for Solomonoff convergence.