Institutional Repository
| Universal computably enumerable sets and initial segment prefix-free complexity | |
| Barmpalias, George | |
| 2013 | |
| Source | INFORMATION AND COMPUTATION
 |
| ISSN | 0890-5401 |
| Volume | 233Pages:41-59 |
| English Abstract | We show that there are Turing complete computably enumerable sets of arbitrarily low nontrivial initial segment prefix-free complexity. In particular, given any computably enumerable set A with nontrivial prefix-free initial segment complexity, there exists a Turing complete computably enumerable set B with complexity strictly less than the complexity of A. On the other hand it is known that sets with trivial initial segment prefix-free complexity are not Turing complete. Moreover we give a generalization of this result for any finite collection of computably enumerable sets A(i), i < k with nontrivial initial segment prefix-free complexity. An application of this gives a negative answer to a question from a monograph by Downey and Hirschfeldt (also raised in an article by Merkle and Stephan) which asked for minimal pairs in the structure of the c.e. reals ordered by their initial segment prefix-free complexity. Further consequences concern various notions of degrees of randomness. For example, the Solovay degrees and the K-degrees of computably enumerable reals and computably enumerable sets are not elementarily equivalent. Also, the degrees of randomness of c.e. reals based on plain and prefix-free complexity are not elementarily equivalent; the same holds for the degrees of c.e. sets. (C) 2013 Elsevier Inc. All rights reserved.; We show that there are Turing complete computably enumerable sets of arbitrarily low nontrivial initial segment prefix-free complexity. In particular, given any computably enumerable set A with nontrivial prefix-free initial segment complexity, there exists a Turing complete computably enumerable set B with complexity strictly less than the complexity of A. On the other hand it is known that sets with trivial initial segment prefix-free complexity are not Turing complete. Moreover we give a generalization of this result for any finite collection of computably enumerable sets A(i), i < k with nontrivial initial segment prefix-free complexity. An application of this gives a negative answer to a question from a monograph by Downey and Hirschfeldt (also raised in an article by Merkle and Stephan) which asked for minimal pairs in the structure of the c.e. reals ordered by their initial segment prefix-free complexity. Further consequences concern various notions of degrees of randomness. For example, the Solovay degrees and the K-degrees of computably enumerable reals and computably enumerable sets are not elementarily equivalent. Also, the degrees of randomness of c.e. reals based on plain and prefix-free complexity are not elementarily equivalent; the same holds for the degrees of c.e. sets. (C) 2013 Elsevier Inc. All rights reserved. |
| Indexed Type | SCI |
| Keyword | Universal Sets Computably Enumerable Kolmogorov Complexity Initial Segment Complexity |
| Department | Chinese Acad Sci, Inst Software, State Key Lab Comp Sci, Beijing 100190, Peoples R China. |
| Language | 英语 |
| WOS ID | WOS:000330258800004 |
| Citation statistics | |
| Content Type | 期刊论文 |
| URI | http://ir.iscas.ac.cn/handle/311060/16894 |
| Collection | 中国科学院软件研究所 |
| Recommended Citation GB/T 7714 | Barmpalias, George. Universal computably enumerable sets and initial segment prefix-free complexity[J]. INFORMATION AND COMPUTATION,2013,233:41-59. |
| APA | Barmpalias, George.(2013).Universal computably enumerable sets and initial segment prefix-free complexity.INFORMATION AND COMPUTATION,233,41-59. |
| MLA | Barmpalias, George."Universal computably enumerable sets and initial segment prefix-free complexity".INFORMATION AND COMPUTATION 233(2013):41-59. |
| 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