Abstract
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 $\sum_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.