Characterizing the Strongly Jump-Traceable Sets via Randomness

by Noam Greenberg, Denis R. Hirschfeldt, and André Nies

Status: published in Advances in Mathematics 231 (2012) 2252 - 2293.

Availability: journal version and preprint

Abstract. We show that if a set is computable from every superlow 1-random set, then it is strongly jump-traceable. Together with a result by Greenberg and Nies, this theorem shows that the 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 Δ02 set Y such that every Y-computable c.e. set obeys c. To do so, we connect cost function strength and the strength of randomness notions. Together with a theorem by Greenberg and Nies, this result gives a full correspondence between obedience of cost functions and being computable from Δ02 1-random sets.