Characterizing the strongly jump-traceable sets via randomness

Details Characterizing the strongly jump-traceable sets via randomness Characterizing the strongly jump-traceable sets via randomness

2011-09-30

arxiv.org/abs/1109.6749v1

Mathematics

Logic

41 pages

Scientific paper

We show that if a set $A$ is computable from every superlow 1-random set, then $A$ is strongly jump-traceable. This theorem shows that the computably enumerable (c.e.) strongly jump-traceable sets are exactly the c.e.\ sets computable from every superlow 1-random set. We also prove the analogous result for superhighness: a c.e.\ set is strongly jump-traceable if and only if it is computable from every superhigh 1-random set. Finally, we show that for each cost function $c$ with the limit condition there is a 1-random $\Delta^0_2$ set $Y$ such that every c.e.\ set $A \le_T Y$ obeys $c$. To do so, we connect cost function strength and the strength of randomness notions. This result gives a full correspondence between obedience of cost functions and being computable from $\Delta^0_2$ 1-random sets.

Affiliated with

Also associated with

No associations

Rating

Characterizing the strongly jump-traceable sets via randomness 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 Characterizing the strongly jump-traceable sets via randomness, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Characterizing the strongly jump-traceable sets via randomness will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-667932