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

• Verfasst von: Barmpalias, George [VerfasserIn]
• Verfasst von: Fang, Nan [VerfasserIn]
• Verfasst von: 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
• DOI: doi:10.1016/j.jcss.2016.05.004
• Datenträger: Online-Ressource
• Sprache: eng
• Sach-SW: Asymptotic
• Sach-SW: Completeness
• Sach-SW: Complexity
• Sach-SW: Computability
• Sach-SW: Halting probability
• Sach-SW: Kolmogorov
• Sach-SW: Optimal
• Sach-SW: Oracle use
• Sach-SW: Oracles
• K10plus-PPN: 1727462106

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.