Affordable Access

Publisher Website

Kolmogorov complexity and computably enumerable sets

Authors
Journal
Annals of Pure and Applied Logic
0168-0072
Publisher
Elsevier
Volume
164
Issue
12
Identifiers
DOI: 10.1016/j.apal.2013.06.007
Keywords
  • Computably Enumerable Sets
  • Kolmogorov Complexity
  • Relativization

Abstract

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.

There are no comments yet on this publication. Be the first to share your thoughts.