James Propp <jamespropp@gmail.com> wrote:

Question: If Player B is given complete knowledge of the innards of a million bit-guessing algorithms, can B construct an infinite sequence of bits whose score lies between .49 and .51 for *all* of those algorithms?

Certainly. I assume that the square roots of the primes, in binary, to the right of the radix point, are normal ("random") and uncorrelated. If so, consider some subset of the first k primes. B hashes (exclusive-ors) the digit sequences (to the right of the radix point) of the square roots of those primes together to generate the bit sequence. If k is 20, there will be about a million possible algorithms, so A can probably find the correct one (asuming A only tries algorithms in this set). But if k is much more than 20, A doesn't stand a chance.

Of course by ?a million? I mean ?n?, and by .49 and .51 I mean one-half plus epsilon and one-half minus epsilon, with suitable quantifiers.

How large can n be? If k is more than a thousand, converting all mass in the universe into computers and running them all in parallel until the heat death of the universe wouldn't suffice to find B's algorithm. Of course there will be a chance just slightly less than 1/2 that two completely uncorrelated finite bit strings (e.g. A's and B's, if A is clueless) will match slightly more than half the time, but in the long run the proportion of matches will bounce between slightly more than 1/2 and slightly less than 1/2. Regardless of B's algorithm, so long as it produces the same number of 0s and 1s on average, I think it very unlikely that the asymptotic proportion of matches could be anything but 1/2 or 1.

We?ll allow B to consult an oracle that will answer questions about those million bit-guessing algorithms (e.g., the oracle will reveal the truth-status of the Riemann Hypothesis if that?s germane).

If I understand you correctly, B comes up with an algorithm to generate an unending sequence of bits, and A tries to guess the algorithm so as to generate the same sequence (the same other than some finite number of mismatched bits at the beginning before A guesses the correct algorithm, I mean). As such, I don't understand the point in the oracle. If B simply asks the oracle for a complete list of every algorithm A will try, that would make B's already easy task even easier.