The Kucera-Gacs theorem is a landmark result in algorithmic randomness asserting that every real is computable from a Martin-Lof random real. If the computation of the first @math bits of a sequence requires @math bits of the random oracle, then @math is the redundancy of the computation. Kucera implicitly achieved redundancy @math while Gacs used a more elaborate coding procedure which achieves redundancy @math . A similar upper bound is implicit in the later proof by Merkle and Mihailovic. In this paper we obtain strict optimal lower bounds on the redundancy in computations from Martin-Lof random oracles. We show that any nondecreasing computable function @math such that @math is not a general upper bound on the redundancy in computations from Martin-Lof random oracles. In fact, there exists a real @math such that the redundancy @math of any computation of @math from a Martin-Lof random oracle satisfies @math . Moreover, the class of such reals is comeager and includes a @math real as well as all weakly 2-generic reals. This excludes many slow growing functions such as @math from bounding the redundancy in computations from random oracles for a large class of reals. On the other hand it was recently shown that if @math then @math is a general upper bound for the redundancy in computations of any real from some Martin-Lof random oracle. Our results are obtained as an application of a theory of effective betting strategies with restricted wagers which we develop.
Chaitin [G. J. Chaitin, J. Assoc. Comput. Mach. , vol. 22, pp. 329---340, 1975] introduced his Ω number as a concrete example of random real. The real Ω is defined as the probability that an optimal computer halts, where the optimal computer is a universal decoding algorithm used to define the notion of program-size complexity. Chaitin showed Ω to be random by discovering the property that the first n bits of the base-two expansion of Ω solve the halting problem of the optimal computer for all binary inputs of length at most n . In the present paper we investigate this property from various aspects. It is known that the base-two expansion of Ω and the halting problem are Turing equivalent. We consider elaborations of both the Turing reductions which constitute the Turing equivalence. These elaborations can be seen as a variant of the weak truth-table reduction, where a computable bound on the use function is explicitly specified. We thus consider the relative computational power between the base-two expansion of Ω and the halting problem by imposing the restriction to finite size on both the problems. We characterise the asymptotic upper bounds on the use of Chaitin's ź in oracle computations of halting probabilities (i.e. c.e. reals). We show that the following two conditions are equivalent for any computable function h such that h ( n ) - n is non-decreasing: (1) h ( n ) - n is an information content measure, i.e. the series ź n 2 n - h ( n ) converges, (2) for every c.e. real α there exists a Turing functional via which ź computes α with use bounded by h. We also give a similar characterisation with respect to computations of c.e. sets from ź, by showing that the following are equivalent for any computable non-decreasing function g: (1) g is an information-content measure, (2) for every c.e. set A, ź computes A with use bounded by g. Further results and some connections with Solovay functions (studied by a number of authors 38,3,26,11) are given. Optimal oracle-use of Chaitin's Omega number.Qualification and optimization of the completeness of Chaitin's Omega.Tight bounds on oracle use in the computably enumerable sets and reals.