Higher Randomness Notions and Their Lowness Properties
C. T. Chong, André Nies, Liwen Yu · 2007
Abstract. We study randomness notions given by higher recursion theory, establishing the relationships Π 1 1-randomness ⊂ Π 1 1-Martin-Löf randomness ⊂ ∆ 1 1randomness = ∆ 1 1-Martin-Löf randomness. We characterize the set of reals that are low for ∆ 1 1 randomness as precisely those that are ∆ 1 1-traceable. We prove that there is a perfect set of such reals. 1.