Difference randomness
Johanna N. Y. Franklin, Keng Meng Ng · Proceedings of the American Mathematical Society · 2010
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 n -r.e. sets for some given n n . In each case, the n n -r.e. randomness hierarchy collapses for n ≥ 2 n\geq 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-Löf 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-Löf random reals. We also provide a martingale characterization for difference randomness.