Kolmogorov complexity and computably enumerable sets

DOI10.1016/J.APAL.2013.06.007MaRDI QIDQ490655zbMATH OpenOpenAlexFDO

Authors George Barmpalias, Angsheng Li

Publication date 27 August 2015

Published in Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1111.4339

zbMATH Keywords

Kolmogorov complexitycomputably enumerable setsrelativization

Mathematics Subject Classification ID

Algorithmic randomness and dimension (03D32) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Applications of computability and recursion theory (03D80) Other degrees and reducibilities in computability and recursion theory (03D30)

Abstract: 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.

Recommendations

• Universal computably enumerable sets and initial segment prefix-free complexity
• Analogues of Chaitin's Omega in the computably enumerable sets
• Kolmogorov Complexity and Instance Complexity of Recursively Enumerable Sets
• Computuing \(K\)-trivial sets by incomplete random sets
• Kolmogorov complexity of initial segments of sequences and arithmetical definability

Cited in

(17)

• Universal computably enumerable sets and initial segment prefix-free complexity
• New Computational Paradigms
• scientific article; zbMATH DE number 1138314 (Why is no real title available?)
• Kolmogorov Complexity and Instance Complexity of Recursively Enumerable Sets
• scientific article; zbMATH DE number 922628 (Why is no real title available?)
• Complexity properties of recursively enumerable sets and \(bsQ\)-completeness
• Analogues of Chaitin's Omega in the computably enumerable sets
• Kolmogorov entropy in the context of computability theory
• Computably enumerable sets below random sets
• Computably enumerable sets and quasi-reducibility
• ASYMPTOTIC DENSITY AND COMPUTABLY ENUMERABLE SETS
• Kolmogorov complexity of initial segments of sequences and arithmetical definability
• The complexity types of computable sets
• On the number of infinite sequences with trivial initial segment complexity
• HIERARCHIES OF GENERALIZED KOLMOGOROV COMPLEXITIES AND NONENUMERABLE UNIVERSAL MEASURES COMPUTABLE IN THE LIMIT
• Computuing \(K\)-trivial sets by incomplete random sets
• Kobayashi compressibility

This page was built for publication: Kolmogorov complexity and computably enumerable sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q490655)