Navigation überspringen
Universitätsbibliothek Heidelberg
Status: Bibliographieeintrag

Verfügbarkeit
Standort: ---
Exemplare: ---
heiBIB
 Online-Ressource
Verfasst von:Barmpalias, George [VerfasserIn]   i
 Fang, Nan [VerfasserIn]   i
 Lewis-Pye, Andrew [VerfasserIn]   i
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

Permanenter Link auf diesen Titel (bookmarkfähig):  https://katalog.ub.uni-heidelberg.de/titel/68628808   QR-Code
zum Seitenanfang