ON LANGUAGES REDUCIBLE TO ALGORITHMICALLY RANDOM LANGUAGES

In this paper languages ''bounded reducible'' to algorithmically rando m languages are studied; these are the languages whose characteristic sequences are algorithmically random (as defined by Martin-Lof [Inform . and Control, 9(1966), pp.602-619]); here RAND denotes the class of a lgorithmically random languages. The reducibilities less than or equal to(R) are very general but are defined so that if A epsilon R(B), the n there is a machine M with the properties that L(M, B) = A and every computation of M relative to any oracle halts. Book, Lutz, and Wagner [Math. Systems Theory, 27 (1994), pp.201-209] studied ALMOST-R, define d to be [A] for almost every B, A less than or equal to(R) B}. They sh owed that ALMOST-R = R(RAND)boolean AND REC, where REC denotes the cla ss of recursive languages, so that ALMOST-R is the ''recursive part'' of R(RAND). In this paper this characterization is strengthened by sho wing that for every B epsilon RAND, ALMOST-R=R(B)boolean AND REC. A pa ir (A, B) of languages is an independent pair of algorithmically rando m languages if A circle plus B epsilon RAND. In this paper it is shown that for every R and for every independent pair (A, B), ALMOST-R = R( A) boolean AND R(B).