Kolmogorov complexity and computably enumerable sets

ISCAS OpenIR

	Kolmogorov complexity and computably enumerable sets
	Barmpalias, George; Li, Angsheng
	2013
发表期刊	ANNALS OF PURE AND APPLIED LOGIC
ISSN	0168-0072
卷号	164 期号:12 页码:1187-1200
摘要	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
关键词	Computably Enumerable Sets Kolmogorov Complexity Relativization
部门归属	[Barmpalias, George; Li, Angsheng] Chinese Acad Sci, Inst Software, State Key Lab Comp Sci, Beijing 100190, Peoples R China.
语种	英语
WOS记录号	WOS:000324715300003
引用统计	被引频次：2[WOS] [WOS记录] [WOS相关记录]
内容类型	期刊论文
URI标识	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.