Good point. That strategy works not just against a million adversaries but against all of them at once! Can anyone come up with something a bit more constructive? Maybe instead of trying to trounce a million adversaries, we could think about trying to defeat just two. Jim Propp On Thu, Oct 3, 2019 at 9:40 AM Mike Stay <metaweta@gmail.com> wrote:
I want a (nonrandom) construction, not an existence proof.
I'm interpreting "construction" as metamathematical, not limiting the answer to constructive mathematics, and I'm interpreting this as "don't choose a bit string at random", not "don't use algorithmic randomness".
Chaitin's Omega number, like any algorithmically random real, has the property that the shortest program that outputs the first n bits of Omega has length greater or equal to n - c, where c depends only on the choice of prefix-free universal Turing machine. In the limit of large n, none of the bit predictors can do better than chance.
On Thu, Oct 3, 2019 at 5:44 AM James Propp <jamespropp@gmail.com> wrote:
Define a bit-guessing algorithm to be any algorithm that, given a finite string of bits as input, predict what the next bit will be; define the bit-guessing game as an adversarial game in which Player A chooses a bit-guessing algorithm, Player B chooses an infinite sequence of bits,
and
the score is the asymptotic density (maybe I should say upper density or lower density?) of the set of n’s for which A’s algorithm correctly predicts B’s nth bit.
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? 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.
I want a (nonrandom) construction, not an existence proof.
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).
This is probably an old problem, but I’m not sure how to search for it.
Jim Propp _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Mike Stay - metaweta@gmail.com http://math.ucr.edu/~mike https://reperiendi.wordpress.com
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun