UNIFIED CHARACTERIZATIONS OF LOWNESS PROPERTIES VIA KOLMOGOROV

Abstract. Consider a randomness notion C. A uniform test in the sense of C is a total computable procedure that each oracle X produces a test relative to X in the sense of C. We say that a binary sequence Y is C-random uniformly relative to X if Y passes all uniform C tests relative to X. Suppose now we have a pair of randomness notions C and D where C D, for instance Martin-Löf randomness and Schnorr randomness. Several authors have characterized classes of the form Low(C;D) which consist of the oracles X that are so feeble that C DX. Our goal is to do the same when the randomness notion D is relativized uniformly: denote by Low⋆(C;D) the class of oracles X such that every C-random is uniformly D-random relative to X. (1) We show that X 2 Low⋆(MLR; SR) if and only if X is c.e. tt-traceable if and only if X is anticomplex if and only if X is Martin-Löf packing measure zero with respect to all computable dimension functions. (2) We also show that X 2 Low⋆(SR;WR) if and only if X is computably i.o. tt-traceable if and only ifX is not totally complex if and only ifX is Schnorr Hausdorff measure zero with respect to all computable dimension functions. 1