Institutional Repository
| analogues of chaitin's omega in the computably enumerable sets | |
| Barmpalias G.; H&#; lzl R.; Lewis A.E.M.; Merkle W. | |
| 2013 | |
| Source | Information Processing Letters
 |
| ISSN | 0020-0190 |
| Volume | 113Issue:5-6Pages:171-178 |
| English Abstract | We show that there are computably enumerable (c.e.) sets with maximum initial segment Kolmogorov complexity amongst all c.e. sets (with respect to both the plain and the prefix-free version of Kolmogorov complexity). These c.e. sets belong to the weak truth table degree of the halting problem, but not every weak truth table complete c.e. set has maximum initial segment Kolmogorov complexity. Moreover, every c.e. set with maximum initial segment prefix-free complexity is the disjoint union of two c.e. sets with the same property; and is also the disjoint union of two c.e. sets of lesser initial segment complexity. © 2013 Elsevier B.V.; We show that there are computably enumerable (c.e.) sets with maximum initial segment Kolmogorov complexity amongst all c.e. sets (with respect to both the plain and the prefix-free version of Kolmogorov complexity). These c.e. sets belong to the weak truth table degree of the halting problem, but not every weak truth table complete c.e. set has maximum initial segment Kolmogorov complexity. Moreover, every c.e. set with maximum initial segment prefix-free complexity is the disjoint union of two c.e. sets with the same property; and is also the disjoint union of two c.e. sets of lesser initial segment complexity. © 2013 Elsevier B.V. |
| Indexed Type | EI |
| Keyword | Computer Applications Data Processing |
| Department | (1) State Key Lab of Computer Science Institute of Software Chinese Academy of Sciences P.O. Box 8718 Beijing 100190 China; (2) Bureau 6A35 LIAFA 175 rue du Chevaleret 75013 Paris France; (3) School of Mathematics University of Leeds LS2 9JT Leeds United Kingdom; (4) Institut für Informatik Ruprecht-Karls-Universität Heidelberg Germany |
| Language | 英语 |
| WOS ID | WOS:000316037700005 |
| Citation statistics | |
| Content Type | 期刊论文 |
| URI | http://ir.iscas.ac.cn/handle/311060/15228 |
| Collection | 中国科学院软件研究所 |
| Recommended Citation GB/T 7714 | Barmpalias G.,H&#,lzl R.,et al. analogues of chaitin's omega in the computably enumerable sets[J]. Information Processing Letters,2013,113(5-6):171-178. |
| APA | Barmpalias G.,H&#,lzl R.,Lewis A.E.M.,&Merkle W..(2013).analogues of chaitin's omega in the computably enumerable sets.Information Processing Letters,113(5-6),171-178. |
| MLA | Barmpalias G.,et al."analogues of chaitin's omega in the computably enumerable sets".Information Processing Letters 113.5-6(2013):171-178. |
| 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