Comparing notions of randomness
It is an open problem in the area of effective (algorithmic) randomness whether Kolmogorov-Loveland randomness coincides with Martin-Lof randomness. Joe Miller and Andre Nies suggested some variations of Kolmogorov-Loveland randomness to approach this problem and to provide a partial solution. We show that their proposed notion of injective randomness is still weaker than Martin-Lof randomness. Since in this proof some of the ideas we use are clearer, we also show the weaker theorem that permutation randomness is weaker than Martin-Lof randomness. (C) 2009 Elsevier B.V. All rights reserved.
kolmogorov-loveland randomness martin-lof randomness effective randomness