Kolmogorov complexity and computably enumerable sets
文献类型：期刊论文
| 作者 | Barmpalias, George ; Li, Angsheng |
| 刊名 | ANNALS OF PURE AND APPLIED LOGIC
 |
| 出版日期 | 2013 |
| 卷号 | 164期号:12页码:1187-1200 |
| 关键词 | Computably enumerable sets Kolmogorov complexity Relativization |
| ISSN号 | 0168-0072 |
| 中文摘要 | We study the computably enumerable sets in terms of the: (a) Kolmogorov complexity of their initial segments; (b) Kolmogorov complexity of finite programs when they are used as oracles. We present an extended discussion of the existing research on this topic, along with recent developments and open problems. Besides this survey, our main original result is the following characterization of the computably enumerable sets with trivial initial segment prefix-free complexity. A computably enumerable set A is K-trivial if and only if the family of sets with complexity bounded by the complexity of A is uniformly computable from the halting problem. (C) 2013 Elsevier B.V. All rights reserved. |
| 英文摘要 | We study the computably enumerable sets in terms of the: (a) Kolmogorov complexity of their initial segments; (b) Kolmogorov complexity of finite programs when they are used as oracles. We present an extended discussion of the existing research on this topic, along with recent developments and open problems. Besides this survey, our main original result is the following characterization of the computably enumerable sets with trivial initial segment prefix-free complexity. A computably enumerable set A is K-trivial if and only if the family of sets with complexity bounded by the complexity of A is uniformly computable from the halting problem. (C) 2013 Elsevier B.V. All rights reserved. |
| 收录类别 | SCI |
| 语种 | 英语 |
| WOS记录号 | WOS:000324715300003 |
| 公开日期 | 2014-12-16 |
| 源URL | [http://ir.iscas.ac.cn/handle/311060/16900]  |
| 专题 | 软件研究所_软件所图书馆_期刊论文 |
| 推荐引用方式 GB/T 7714 | Barmpalias, George,Li, Angsheng. Kolmogorov complexity and computably enumerable sets[J]. ANNALS OF PURE AND APPLIED LOGIC,2013,164(12):1187-1200. |
| APA | Barmpalias, George,&Li, Angsheng.(2013).Kolmogorov complexity and computably enumerable sets.ANNALS OF PURE AND APPLIED LOGIC,164(12),1187-1200. |
| MLA | Barmpalias, George,et al."Kolmogorov complexity and computably enumerable sets".ANNALS OF PURE AND APPLIED LOGIC 164.12(2013):1187-1200. |
入库方式： OAI收割
来源：软件研究所
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。