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 Ω 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 conten...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article (Journal) |
| Language: | English |
| Published: |
11June2016
|
| In: |
Journal of computer and system sciences
Year: 2016, Volume: 82, Issue: 8, Pages: 1283-1299 |
| ISSN: | 1090-2724 |
| DOI: | 10.1016/j.jcss.2016.05.004 |
| Online Access: | Verlag, lizenzpflichtig, Volltext: https://doi.org/10.1016/j.jcss.2016.05.004 Verlag, lizenzpflichtig, Volltext: http://www.sciencedirect.com/science/article/pii/S0022000016300307 
|
| Author Notes: | George Barmpalias, Nan Fang, Andrew Lewis-Pye |
| Summary: | 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 ∑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. |
|---|---|
| Item Description: | Gesehen am 19.08.2020 |
| Physical Description: | Online Resource |
| ISSN: | 1090-2724 |
| DOI: | 10.1016/j.jcss.2016.05.004 |