Kolmogorov complexity and computably enumerable sets

DOI10.1016/J.APAL.2013.06.007zbMATH Open1320.03073arXiv1111.4339OpenAlexW2964261109MaRDI QIDQ490655FDOQ490655

Authors: George Barmpalias, Angsheng Li 

Publication date: 27 August 2015

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

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.

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

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

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)

Cited In (16)

• Universal computably enumerable sets and initial segment prefix-free complexity
• Title not available (Why is that?)
• Title not available (Why is that?)
• 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
• New Computational Paradigms
• 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)