Keep in mind that I'm talking about SI where the programs output single values as predictions, instead of probability distributions.
Let's reformulate it in terms of games. For example, asking SI to output probabilities is equivalent to making it play a game where rewards are proportional to log score. As far as I can tell, you're talking about a different game where SI outputs a single guess at each step, and wins a dollar for each correct guess. In that game I do know several ways to construct input sequences that allow a human to beat SI by an unbounded amount of money, but I'd be surprised if a sequence of i.i.d. random bits was also such a sequence. And I'd be even more surprised if it depended on the encoding of programs used by SI. Not saying that you're wrong, but can you try to sketch a more detailed proof? In particular, can you explain how it gets around the fact that SI's probability of the next bit being 1 converges to 5/6?
I'm saying that SI's probability of next bit being 1 doesn't converge to 5/6, for some encodings and (very importantly) using single outputs instead of probability distributions.
For example, suppose we take a program encoding where it does converge to 5/6 then expand it so every "0" becomes a "00" and every "1" becomes a "01". Then we add rules to the encoding such that, for every "10" or "11" starting at an even position (so the original re-coding would have none), an extra zero is appended to th...
So, I've been hearing a lot about the awesomeness of Solomonoff induction, at least as a theoretical framework. However, my admittedly limited understanding of Solomonoff induction suggests that it would form an epicly bad hypothesis if given a random string. So my question is, if I misunderstood, how does it deal with randomness? And if I understood correctly, isn't this a rather large gap?
Edit: Thanks for all the comments! My new understanding is that Solomonoff induction is able to understand that it is dealing with a random string (because it finds itself giving equal weight to programs that output a 1 or a 0 for the next bit), but despite that is designed to keep looking for a pattern forever. While this is a horrible use of resources, the SI is a theoretical framework that has infinite resources, so that's a meaningless criticism. Overall this seems acceptable, though if you want to actually implement a SI you'll need to instruct it on giving up. Furthermore, the SI will not include randomness as a distinct function in its hypothesis, which could lead to improper weighting of priors, but will still have good predictive power -- and considering that Solomonoff induction was only meant for computable functions, this is a pretty good result.