HIERARCHIES OF RANDOMNESS TESTS

Abstract

ABSTRACT. It is well known that Martin-Löf randomness can be characterized by a number of equivalent test concepts, based either on effective nullsets (Martin-Löf and Solovay tests) or on prefix-free Kolmogorov complexity (lower and upper entropy). These equivalences are not preserved as regards the partial randomness notions induced by effective Hausdorff measures or partial incompressibility. Tadaki [21] and Calude, Staiger and Terwijn [2] studied several concepts of partial randomness, but for some of them the exact relations remained unclear. In this paper we will show that they form a proper hierarchy of randomness notions, namely for any ρ of the form ρ(x) = 2 −|x|s with s being a rational number satisfying 0 < s < 1, the Martin-Löf ρ-tests are strictly weaker than Solovay ρ-tests which in turn are strictly weaker than strong Martin-Löf ρ-tests. These results also hold for a more general class of ρ introduced as unbounded premeasures. 1.