Status: Bibliographieeintrag
Standort: ---
Exemplare:
---
| Online-Ressource |
Verfasst von: | Barmpalias, George [VerfasserIn]  |
| Fang, Nan [VerfasserIn]  |
| Lewis-Pye, Andrew [VerfasserIn]  |
Titel: | Optimal asymptotic bounds on the oracle use in computations from Chaitin's omega |
Verf.angabe: | George Barmpalias, Nan Fang, Andrew Lewis-Pye |
E-Jahr: | 2016 |
Jahr: | 11June2016 |
Umfang: | 17 S. |
Fussnoten: | Gesehen am 19.08.2020 |
Titel Quelle: | Enthalten in: Journal of computer and system sciences |
Ort Quelle: | San Diego, Calif. [u.a.] : Elsevier, 1967 |
Jahr Quelle: | 2016 |
Band/Heft Quelle: | 82(2016), 8, Seite 1283-1299 |
ISSN Quelle: | 1090-2724 |
Abstract: | 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. |
DOI: | doi:10.1016/j.jcss.2016.05.004 |
URL: | Bitte beachten Sie: Dies ist ein Bibliographieeintrag. Ein Volltextzugriff für Mitglieder der Universität besteht hier nur, falls für die entsprechende Zeitschrift/den entsprechenden Sammelband ein Abonnement besteht oder es sich um einen OpenAccess-Titel handelt.
Volltext ; Verlag: https://doi.org/10.1016/j.jcss.2016.05.004 |
| Volltext: http://www.sciencedirect.com/science/article/pii/S0022000016300307 |
| DOI: https://doi.org/10.1016/j.jcss.2016.05.004 |
Datenträger: | Online-Ressource |
Sprache: | eng |
Sach-SW: | Asymptotic |
| Completeness |
| Complexity |
| Computability |
| Halting probability |
| Kolmogorov |
| Optimal |
| Oracle use |
| Oracles |
K10plus-PPN: | 1727462106 |
Verknüpfungen: | → Zeitschrift |
Optimal asymptotic bounds on the oracle use in computations from Chaitin's omega / Barmpalias, George [VerfasserIn]; 11June2016 (Online-Ressource)
68628808