DIFFERENCE RANDOMNESS

In this paper, we define new notions of randomness based on the difference hierarchy. We consider various ways in which a real can avoid all effectively given tests consisting of n-r.e. sets for some given n. In each case, the n-r.e. randomness hierarchy collapses for n >= 2. In one case, we call the resulting notion difference randomness and show that it results in a class of random reals that is a strict subclass of the Martin-Lof random reals and a proper superclass of both the Demuth random and weakly 2-random reals. In particular, we are able to characterize the difference random reals as the Turing incomplete Martin-Lof random reals. We also provide a martingale characterization for difference randomness.