Institutional Repository
| Kolmogorov complexity and computably enumerable sets | |
| Barmpalias, George; Li, Angsheng | |
| 2013 | |
| Source | ANNALS OF PURE AND APPLIED LOGIC
 |
| ISSN | 0168-0072 |
| Volume | 164Issue:12Pages:1187-1200 |
| English Abstract | 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. |
| Indexed Type | SCI |
| Keyword | Computably Enumerable Sets Kolmogorov Complexity Relativization |
| Department | [Barmpalias, George; Li, Angsheng] Chinese Acad Sci, Inst Software, State Key Lab Comp Sci, Beijing 100190, Peoples R China. |
| Language | 英语 |
| WOS ID | WOS:000324715300003 |
| Citation statistics | |
| Content Type | 期刊论文 |
| URI | http://ir.iscas.ac.cn/handle/311060/16900 |
| Collection | 中国科学院软件研究所 |
| Recommended Citation 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. |
| Files in This Item: | There are no files associated with this item. | |||||
Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.
Edit Comment