Computational randomness and lowness
- 1 September 2001
- journal article
- Published by Cambridge University Press (CUP) in The Journal of Symbolic Logic
- Vol. 66 (3) , 1199-1205
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.Keywords
This publication has 6 references indexed in Scilit:
- Randomness in computability theory2000
- Measure, Π 1 0 -classes and complete extensions of PA1985
- A mathematical proof of S. Shelah’s theorem on the measure problem and related resultsIsrael Journal of Mathematics, 1984
- Zufälligkeit und Wahrscheinlichkeit1971
- The Degrees of Hyperimmune SetsMathematical Logic Quarterly, 1968
- The definition of random sequencesInformation and Control, 1966