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

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 ∑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], [11]) are given.

Citation

@article{BARMPALIAS20161283,
author = {George Barmpalias and Nan Fang and Andrew Lewis-Pye},
doi = {https://doi.org/10.1016/j.jcss.2016.05.004},
issn = {0022-0000},
journal = {Journal of Computer and System Sciences},
keywords = {Halting probability, Oracle use, Oracles, Optimal, Asymptotic, Kolmogorov, Completeness, Computability, Complexity},
number = {8},
pages = {1283 - 1299},
title = {Optimal asymptotic bounds on the oracle use in computations from Chaitin's Omega},
url = {http://www.sciencedirect.com/science/article/pii/S0022000016300307},
volume = {82},
year = {2016}
}