much like how halting oracles (which you need to run Solomonoff Induction) are nowhere in the hypotheses which Solomonoff considers
The Solomonoff prior is a mixture over semi-measures[*] that are lower semi-computable: that is, you can compute increasingly good approximations of the semi-measure from below that converge eventually to the actual semi-measure, but at finite time you don’t know how close you are to the right answer. The Solomonoff prior itself is also a lower semi-computable semi-measure. Therefore, there is a real sense in which its hypothesis class includes things as difficult to compute as it is. That being said, my guess is that halting oracles would indeed let you compute more than just the lower semi-computable functions, and it’s also true that being able to run Solomonoff induction would also let you build a halting oracle.
[*] semi-measures are probability distributions that have ‘missing density’, where the probability of a 0 and then a 0, plus the probability of a 0 and then a 1, is less than or equal to the probability of a 0, even though there aren’t any other options in the space for what happens next.
The problem with lower semicomputable functions is that it’s a class not closed under natural operations. For example, taking minus such a function we get an upper semicomputable function that can fail to be lower semicomputable. So, given a Solomonoff induction oracle we can very easily (i.e. using a very efficient oracle machine) construct measures that are not absolutely continuous w.r.t. the Solomonoff prior.
In fact, for any prior this can be achieved by constructing an “anti-inductive” sequence: a sequence that contains 1 at a given place if and only if the prior, conditional on the sequence before this place, assigns probability less than 12 to 1. Such a sequence cannot be accurately predicted by the prior (and, by the merging-of-opinions theorem, a delta-function at this sequence it is not absolutely continuous w.r.t. the prior).
Therefore, there is a real sense in which its hypothesis class includes things as difficult to compute as it is. That being said, my guess is that halting oracles would indeed let you compute more than just the lower semi-computable functions, and it’s also true that being able to run Solomonoff induction would also let you build a halting oracle.
I guess the way to reconcile this is to think that there’s a difference between what you can lower semi-compute, and what you could compute if you could compute lower semi-computable things? But it’s been a while since I had a good understanding of this type of thing.
The Solomonoff prior is a mixture over semi-measures[*] that are lower semi-computable: that is, you can compute increasingly good approximations of the semi-measure from below that converge eventually to the actual semi-measure, but at finite time you don’t know how close you are to the right answer. The Solomonoff prior itself is also a lower semi-computable semi-measure. Therefore, there is a real sense in which its hypothesis class includes things as difficult to compute as it is. That being said, my guess is that halting oracles would indeed let you compute more than just the lower semi-computable functions, and it’s also true that being able to run Solomonoff induction would also let you build a halting oracle.
[*] semi-measures are probability distributions that have ‘missing density’, where the probability of a 0 and then a 0, plus the probability of a 0 and then a 1, is less than or equal to the probability of a 0, even though there aren’t any other options in the space for what happens next.
The problem with lower semicomputable functions is that it’s a class not closed under natural operations. For example, taking minus such a function we get an upper semicomputable function that can fail to be lower semicomputable. So, given a Solomonoff induction oracle we can very easily (i.e. using a very efficient oracle machine) construct measures that are not absolutely continuous w.r.t. the Solomonoff prior.
In fact, for any prior this can be achieved by constructing an “anti-inductive” sequence: a sequence that contains 1 at a given place if and only if the prior, conditional on the sequence before this place, assigns probability less than 12 to 1. Such a sequence cannot be accurately predicted by the prior (and, by the merging-of-opinions theorem, a delta-function at this sequence it is not absolutely continuous w.r.t. the prior).
I guess the way to reconcile this is to think that there’s a difference between what you can lower semi-compute, and what you could compute if you could compute lower semi-computable things? But it’s been a while since I had a good understanding of this type of thing.