Keep in mind that I'm talking about SI where the programs output single values as predictions, instead of probability distributions. So each is eliminated all at once or not at all, instead of being proportionally penalized.
An example where SI will do worse is if your program encoding simply makes it easier to output a zero than a one. For example, if the program encoding is ternary and twos must mean "OutputAnotherZeroOnHalt". This makes twos totally useless except for appending zeroes to your output. In that case extending the best-performing programs (as must be done to predict more partially-compressible values) is going to tend to introduce a lot more zeroes than the thing being modeled would. This will skew the predictions towards "next value zero" by a fixed amount, no matter how long you run the inductor.
The point of SI is that the bias inherent with the choice of the universal Turing machine is washed out as more data are observed.
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.