Optimal asymptotic bounds on the oracle use in computations from Chaitin's Omega
文献类型：期刊论文
| 作者 | Barmpalias, G ; Fang, N ; Lewis-Pye, A |
| 刊名 | JOURNAL OF COMPUTER AND SYSTEM SCIENCES
 |
| 出版日期 | 2016 |
| 卷号 | 82期号:8页码:1283-1299 |
| 关键词 | Halting probability Oracle use Oracles Optimal Asymptotic Kolmogorov Completeness Computability Complexity |
| ISSN号 | 0022-0000 |
| 中文摘要 | 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. |
| 收录类别 | SCI |
| 语种 | 英语 |
| WOS记录号 | WOS:000380383700005 |
| 公开日期 | 2016-12-09 |
| 源URL | [http://ir.iscas.ac.cn/handle/311060/17291]  |
| 专题 | 软件研究所_软件所图书馆_期刊论文 |
| 推荐引用方式 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. |
入库方式： OAI收割
来源：软件研究所
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。