Institutional Repository
| Optimal asymptotic bounds on the oracle use in computations from Chaitin's Omega | |
| Barmpalias, G; Fang, N; Lewis-Pye, A | |
| 2016 | |
| Source | JOURNAL OF COMPUTER AND SYSTEM SCIENCES
 |
| ISSN | 0022-0000 |
| Volume | 82Issue:8Pages:1283-1299 |
| English 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 Sigma(n) 2(n-h(n)) converges, (2) for every c.e. real alpha there exists a Turing functional via which Omega computes alpha with use bounded by h. We also give a similar characterisation with respect to computations of c.e. sets from Omega, 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, Omega 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. (C) 2016 Elsevier Inc. All rights reserved.; 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 Sigma(n) 2(n-h(n)) converges, (2) for every c.e. real alpha there exists a Turing functional via which Omega computes alpha with use bounded by h. We also give a similar characterisation with respect to computations of c.e. sets from Omega, 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, Omega 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. (C) 2016 Elsevier Inc. All rights reserved. |
| Indexed Type | SCI |
| Keyword | Halting Probability Oracle Use Oracles Optimal Asymptotic Kolmogorov Completeness Computability Complexity |
| Department | Chinese Acad Sci, Inst Software, State Key Lab Comp Sci, Beijing, Peoples R China.Victoria Univ Wellington, Sch Math Stat & Operat Res, Wellington, New Zealand. [Fang, Nan] Heidelberg Univ, Inst Informat, D-69115 Heidelberg, Germany. [Lewis-Pye, Andrew] London Sch Econ, Dept Math, Columbia House,Houghton St, London WC2A 2AE, England. |
| Language | 英语 |
| WOS ID | WOS:000380383700005 |
| Citation statistics | |
| Content Type | 期刊论文 |
| URI | http://ir.iscas.ac.cn/handle/311060/17291 |
| Collection | 中国科学院软件研究所 |
| Recommended Citation GB/T 7714 | Barmpalias, G,Fang, N,Lewis-Pye, A. Optimal asymptotic bounds on the oracle use in computations from Chaitin's Omega[J]. JOURNAL OF COMPUTER AND SYSTEM SCIENCES,2016,82(8):1283-1299. |
| APA | Barmpalias, G,Fang, N,&Lewis-Pye, A.(2016).Optimal asymptotic bounds on the oracle use in computations from Chaitin's Omega.JOURNAL OF COMPUTER AND SYSTEM SCIENCES,82(8),1283-1299. |
| MLA | Barmpalias, G,et al."Optimal asymptotic bounds on the oracle use in computations from Chaitin's Omega".JOURNAL OF COMPUTER AND SYSTEM SCIENCES 82.8(2016):1283-1299. |
| Files in This Item: | ||||||
| File Name/Size | DocType | Version | Access | License | ||
| Optimal asymptotic b（571KB） | 开放获取 | License | Application Full Text | |||
Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.
Edit Comment