Lower bounds on the redundancy in computations from random oracles via betting strategies with restricted wagers

摘要

The Kucera-Gacs theorem is a landmark result in algorithmic randomness asserting that every real is computable from a Martin-Loef random real. If the computation of the first n bits of a sequence requires n + h(n) bits of the random oracle, then h is the redundancy of the computation. Kucera implicitly achieved redundancy n log n while Gacs used a more elaborate coding procedure which achieves redundancy n~(1/2) log n. A similar bound is implicit in the later proof by Merkle and Mihailovic. In this paper we obtain optimal strict lower bounds on the redundancy in computations from Martin-Loef random oracles. We show that any nondecreasing computable function g such that Σ_n 2~(-g(n) = ∞ is not a general upper bound on the redundancy in computations from Martin-Ldf random oracles. In fact, there exists a real X such that the redundancy g of any computation of X from a Martin-Loef random oracle satisfies Σ_n 2~(-g(n) < ∞. Moreover, the class of such reals is comeager and includes a Δ_2~0 real as well as all weakly 2-generic reals. On the other hand, it has been recently shown that any real is computable from a Martin-Ltif random oracle with redundancy g, provided that g is a computable nondecreasing function such that Σ_n 2~(-g(n)) < ∞. Hence our lower bound is optimal, and excludes many slow growing functions such as logn from bounding the redundancy in computations from random oracles for a large class of reals. Our results are obtained as an application of a theory of effective betting strategies with restricted wagers which we develop.