Journal of Symbolic Logic · 2001 · 96 citations · 4 references
Natural SciencesComputer ScienceMathematicsProbability TheorySet TheoryTheory Of ComputationRandomized ComputationRecursion TheoryRecursionTuring Degrees
Abstract We prove that there are uncountably many sets that are low for the class of Schnorr random reals. We give a purely recursion theoretic characterization of these sets and show that they all have Turing degree incomparable to 0′. This contrasts with a result of Kučera and Terwijn [5] on sets that are low for the class of Martin-Löf random reals.
4
The definition of random sequences
Per Martin-Löf · Information and Control · 1966 · 1.2K citations
The Degrees of Hyperimmune Sets
Webb Miller, Donald A. Martin · Mathematical logic quarterly · 1968 · 91 citations