Jump inversions inside effectively closed sets
and applications to randomness


G. Barmpalias, R. Downey and K.-M. Ng

Summary


We study inversions of the jump operator on effectively closed sets, combined with certain basis theorems. These jump inversions have implications to the study of the jump operator on the random degrees---for various notions of randomness. For example we characterize the jumps of the weakly 2-random sets which are not 2-random, and the jumps of sets which are weakly 1-random relative to the halting problem but are not 2-random: both of the classes coincide with the degrees above the halting problem which are hyperimmune relative to the halting problem. A further application is the complete solution of Problem 3.6.9 from the book of Nies: one direction of van Lambalgen's theorem holds for weak 2-randomness, while the other fails.

Finally we discuss various techniques for coding information into incomplete randoms. To this end, we give a negative answer to Problem 8.2.14 of the book of Nies: not all weakly 2-random sets are array computable. In fact, given any oracle X, there is a weakly 2-random which is not array computable relative to X. This contrasts with the fact that all 2-random sets are array computable.