Optimal asymptotic bounds on the oracle use in computations from Chaitin's Omega

•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.

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)−nh(n)−n is non-decreasing: (1) h(n)−nh(n)−n is an information content measure, i.e. the series ∑n2n−h(n)∑n2n−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] and [11]) are given.