Universal computably enumerable sets and initial segment prefix-free complexity

Details Universal computably enumerable sets and initial segment prefix-free complexity Universal computably enumerable sets and initial segment prefix-free complexity

2011-10-09

arxiv.org/abs/1110.1864v2

Mathematics

Logic

Scientific paper

We show that there are Turing complete computably enumerable sets of arbitrarily low non-trivial initial segment prefix-free complexity. In particular, given any computably enumerable set $A$ with non-trivial prefix-free initial segment complexity, there exists a Turing complete computably enumerable set $B$ with complexity strictly less than the complexity of $A$. On the other hand it is known that sets with trivial initial segment prefix-free complexity are not Turing complete. Moreover we give a generalization of this result for any finite collection of computably enumerable sets $A_i, i

Affiliated with

Also associated with

No associations

Rating

Universal computably enumerable sets and initial segment prefix-free complexity 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 Universal computably enumerable sets and initial segment prefix-free complexity, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Universal computably enumerable sets and initial segment prefix-free complexity will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-88412