Weakly Useful Sequences

. An infinite binary sequence x is defined to be 1. strongly useful if there is a recursive time bound within which every recursive sequence is Turing reducible to x; and 2. weakly useful if there is a recursive time bound within which all the sequences in a non-measure 0 subset of the set of recursive sequences are Turing reducible to x. Juedes, Lathrop, and Lutz (1994) proved that every weakly useful sequence is strongly deep in the sense of Bennett (1988) and asked whether there are sequences that are weakly useful but not strongly useful. The present paper answers this question affirmatively. The proof is a direct construction that combines the recent martingale diagonalization technique of Lutz (1994) with a new technique, namely, the construction of a sequence that is "recursively deep" with respect to an arbitrary, given uniform reducibility. The abundance of such recursively deep sequences is also proven and used to show that every weakly useful sequence is recursively deep ..