I mentioned to you a few days ago (in chat) that Scholarpedia stated:
The universal a priori probability m has many remarkable properties. A theorem of L.A. Levin states that among the lower semi-computable semi-measures it is the largest such function in the following sense: If p is a lower semi-computable semi-measure, then there is a constant c such that cm(x) >= p(x) for all x.
When you say "The tricky part for me was proving the equivalence of two views of the Solomonoff prior" do you mean you tried to re-derive this result?
For the discrete version, doesn't this boil down to converting a program that semi-computes a semi-measure into a program that "semi-samples from" a semi-measure?
Which is pretty straightforward:
We interpret the remainder of our (infinite) input as a real number y in [0,1]. Every time the measure that we're semi-computing adds an amount p of probability to one of its possible values v, we increment a variable x (which was initialised to 0) by p. If and when x finally exceeds y, we return the value v whose probability was just incremented.
(The con...
Shane Legg's text Solomonoff Induction has helped me a lot over the last few days. I was trying to iron out the kinks in my understanding of Eliezer's argument in this old thread:
Eliezer's statement is correct (more precisely, a computable human cannot beat Solomonoff in accumulated log scores by more than a constant, even if the universe is uncomputable and loves the human), but understanding his purported proof is tricky. Legg's text doesn't give any direct answer to the question at hand, but all the technical details in there, like the difference between "measures" and "semimeasures", are really damn important if you want to work out the answer for yourself. I know mathematics has many areas where an "intuitive understanding" kinda sorta suffices. This is not one of those areas.