analogues of chaitin's omega in the computably enumerable sets

ISCAS OpenIR

	analogues of chaitin's omega in the computably enumerable sets
	Barmpalias G.; H&#; lzl R.; Lewis A.E.M.; Merkle W.
	2013
发表期刊	Information Processing Letters
ISSN	0020-0190
卷号	113 期号:5-6 页码:171-178
摘要	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.
收录类别	EI
关键词	Computer Applications Data Processing
部门归属	(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
语种	英语
WOS记录号	WOS:000316037700005
引用统计
内容类型	期刊论文
URI标识	http://ir.iscas.ac.cn/handle/311060/15228
专题	中国科学院软件研究所
推荐引用方式 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.