Kolmogorov complexity and computably enumerable sets

Details Kolmogorov complexity and computably enumerable sets Kolmogorov complexity and computably enumerable sets

2011-11-18

arxiv.org/abs/1111.4339v1

Mathematics

Logic

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Kolmogorov complexity and computably enumerable sets does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Kolmogorov complexity and computably enumerable sets, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Kolmogorov complexity and computably enumerable sets will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-549072