An anytime algorithm for mixing the computable measures

Epistemic status: Not peer reviewed, high chance of typos and small chance of errors. Written entirely by me, checked by Fable. In this post I prove the existence of an anytime computable Bayesian mixture of all computable measures called , and briefly argue that this is a reasonable alternative to Solomonoff induction's universal distribution for general sequence prediction. I believe that Tom Sterkenburg told me that this is possible, but I could not find it written down anywhere (though I may have missed it!). Indeed, has been conjectured not to be limit=anytime computable by Hutter and Muchnik: https://arxiv.org/abs/cs/0407057 . I worked out the anytime algorithm with @Aram Ebtekar and @Marcus Hutter , though any mistakes are mine. Anytime computable (or limit computable): A function f is anytime computable if where is finitely computable. Lower semicomputable (or l.s.c.): A function f is l.s.c. if where is non-decreasing in t. Computable (or estimable): A function f is computable if where . A sequence predictor is a function from the binary strings to [0,1] which we interpret as the probability of seeing the prefix. Assuming "superadditivity" , specifies a (unique) distribution on possibly infinite sequences. The function is also called a semimeasure. Measures satisfy superadditivity with equality, which is called additivity. Solomonoff induction predicts with the universal distribution , which is lower semicomputable but (only) has anytime computable posteriors. is a u…