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