Characterizing the strongly jump-traceable sets via randomness

Original · EN

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 Δ⁰₂ set Y such that every c.e.set A ≤ₜ 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 Δ⁰₂ 1-random sets.