The Journal of Symbolic Logic

Research Article

Lowness for Kurtz randomness

Noam Greenberga1 and Joseph S. Millera2

a1 School of Mathematics, Statistics and Computer Science, Victoria University, P.O. Box 600, Wellington, New Zealand, E-mail: greenberg@msor.vuw.ac.nz

a2 Department of Mathematics, University of Wisconsin, Madison. Wi 53706-1388., USA, E-mail: jmiller@math.wisc.edu

Abstract

We prove that degrees that are low for Kurtz randomness cannot be diagonally non-recursive. Together with the work of Stephan and Yu [16], this proves that they coincide with the hyperimmune-free non-DNR degrees, which are also exactly the degrees that are low for weak 1-genericity.

We also consider Low(, Kurtz), the class of degrees a such that every element of is a-Kurtz random. These are characterised when is the class of Martin-Löf random, computably random, or Schnorr random reals. We show that Low(ML, Kurtz) coincides with the non-DNR degrees, while both Low(CR, Kurtz) and Low(Schnorr, Kurtz) are exactly the non-high, non-DNR degrees.

(Received April 18 2008)