If there is no computable regularity, then no prior can do well. In fact, the Solomonoff prior does just as well asymptotically as any computable prior.

This seems to be a common belief. But see this discussion I had with Eliezer where I offered some good arguments and counterexamples against it.

The link goes to the middle, most relevant part of the discussion. But if you look at the top of it, I'm not arguing against the Solomonoff approach, but instead trying to find a generalization of it that makes more sense.

I've linked to that discussion several times in my comments here, but I guess many people still haven't seen it. Maybe I should make a top-level post about it?