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

We characterise the asymptotic upper bounds on the use of Chaitin's Omega 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 Sigma(n) 2(n-h(n)) converges, (2) for every c.e. real alpha there exists a Turing functional via which Omega computes alpha with use bounded by h. We also give a similar characterisation with respect to computations of c.e. sets from Omega, 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, Omega 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. (C) 2016 Elsevier Inc. All rights reserved.