Universal computably enumerable sets and initial segment prefix-free complexity

ISCAS OpenIR

	Universal computably enumerable sets and initial segment prefix-free complexity
	Barmpalias, George
	2013
发表期刊	INFORMATION AND COMPUTATION
ISSN	0890-5401
卷号	233 页码:41-59
摘要	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.
收录类别	SCI
关键词	Universal Sets Computably Enumerable Kolmogorov Complexity Initial Segment Complexity
部门归属	Chinese Acad Sci, Inst Software, State Key Lab Comp Sci, Beijing 100190, Peoples R China.
语种	英语
WOS记录号	WOS:000330258800004
引用统计
内容类型	期刊论文
URI标识	http://ir.iscas.ac.cn/handle/311060/16894
专题	中国科学院软件研究所
推荐引用方式 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.