Kolmogorov complexity and computably enumerable sets

被引:2
作者
Barmpalias, George [1 ]
Li, Angsheng [1 ]
机构
[1] Chinese Acad Sci, Inst Software, State Key Lab Comp Sci, Beijing 100190, Peoples R China
基金
中国国家自然科学基金;
关键词
Computably enumerable sets; Kolmogorov complexity; Relativization; INITIAL SEGMENT COMPLEXITY; RANDOMNESS; LOWNESS; SOLOVAY;
D O I
10.1016/j.apal.2013.06.007
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
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.
引用
收藏
页码:1187 / 1200
页数:14
相关论文
共 61 条
[1]   Maximal Pairs of Computably Enumerable Sets in the Computably Lipschitz Degrees [J].
Ambos-Spies, Klaus ;
Ding, Decheng ;
Fan, Yun ;
Merkle, Wolfgang .
THEORY OF COMPUTING SYSTEMS, 2013, 52 (01) :2-27
[2]  
[Anonymous], 1989, Kolmogorov Complexity and Its Applications
[3]  
[Anonymous], 1987, PERSPECTIVES MATH LO
[4]  
[Anonymous], 1965, PROBL PEREDACHI INF
[5]   On the Gap Between Trivial and Nontrivial Initial Segment Prefix-Free Complexity [J].
Baartse, Martijn ;
Barmpalias, George .
THEORY OF COMPUTING SYSTEMS, 2013, 52 (01) :28-47
[6]  
Barmpalias G, 2005, LECT NOTES COMPUT SC, V3526, P8
[7]   Analogues of Chaitin's Omega in the computably enumerable sets [J].
Barmpalias, G. ;
Hoelzl, R. ;
Lewis, A. E. M. ;
Merkle, W. .
INFORMATION PROCESSING LETTERS, 2013, 113 (5-6) :171-178
[8]   Randomness, lowness and degrees [J].
Barmpalias, George ;
Lewis, Andrew E. M. ;
Soskova, Mariya .
JOURNAL OF SYMBOLIC LOGIC, 2008, 73 (02) :559-577
[9]   The ibT degrees of computably enumerable sets are not dense [J].
Barmpalias, George ;
Lewis, Andrew E. M. .
ANNALS OF PURE AND APPLIED LOGIC, 2006, 141 (1-2) :51-60
[10]   Compactness arguments with effectively closed sets for the study of relative randomness [J].
Barmpalias, George .
JOURNAL OF LOGIC AND COMPUTATION, 2012, 22 (04) :679-691