Mitchell, thanks. Actually I already know pretty much all this stuff, and have long been interested in some questions about large cardinals and axiom systems. Nice writeup though!
But right now I'm just interested in "the mathematics of Hutter", that is, how far we can extend Levin's original theorem. If you're asking for a rigorous formulation, here's a pretty concise one I just thought up, not sure how much sense it makes. Let's define a "supermartingale with bounded increments" (SWBI) as a function M on finite bit sequences S that satisfies the following conditions:
1) M(empty sequence) = 0
2) for any S, (M(S#0) + M(S#1))/2 <= M(S)
3) for any S, M(S#0) - M(S) <= 1 and M(S#1) - M(S) <= 1
The question: does the set of all lower-semicomputable SWBIs contain an element X that dominates any other element Y up to an additive constant (which may depend on Y but doesn't depend on S)?
Let F be the SWBI that just says F(S) = number of 0s in S - number of 1s in S. Let M be an arbitrary semicomputable SWBI. Then I don't think M can dominate both F and -F up to an additive constant.
I have a vague, handwavy argument:
Suppose the 'data' is an algorithmically random sequence, which basically gives us a discrete random walk. Now a random walk must return infinitely many times to the 'center' (where F = 0). And in order to dominate both F and -F, when the random walk is far away from the center, M is going to have to be increasing at the rate of ...
This will be unparseable to anyone except maybe ten people here. What the hell, I'm posting it anyway.
Consider game 3 from my earlier post: a possibly uncomputable sequence of bits comes in, you're trying to guess the next bit, the payoff for each correct guess is $1. Obviously any deterministic strategy can be humiliated by a sequence of bits that's chosen to make it always guess wrong. User paulfchristiano suggested that multiplicative weights could yield a randomized strategy that does at most a constant worse than any human in expectation. I noted that, unlike the Solomonoff mixture, multiplicative weights over lower-semicomputable randomized strategies is not itself lower-semicomputable (several pages of algebra omitted), so we don't have a strategy that's optimal within its own class. Then I found some slides by Hutter that include a handy table showing how unusual it is for a class do be dominated by a measure within that same class.
So here's the question: is there an analog of "dominant lower-semicomputable semimeasure" for some class of games other than the log-score game? Desiderata: I guess it must correspond to randomized strategies (because deterministic ones are not enough), it must play at most an additive constant worse than any human in expectation (or maybe a multiplicative constant that can be made arbitrarily close to 1 by parameter choice, as with multiplicative weights), and it must be good within its own class of computability (not just superior to all members of some lower class). As far as I can tell, the literature has no answer to this question, and I already spent about a week on it with no success. Anyone here have more understanding than me?