language-icon Old Web
English
Sign In

Continuous higher randomness

2017 
We investigate the role of continuous reductions and continuous relativization in the context of higher randomness. We define a higher analogue of Turing reducibility and show that it interacts well with higher randomness, for example with respect to van Lambalgen’s theorem and the Miller–Yu/Levin theorem. We study lowness for continuous relativization of randomness, and show the equivalence of the higher analogues of the different characterizations of lowness for Martin-Lof randomness. We also characterize computing higher K-trivial sets by higher random sequences. We give a separation between higher notions of randomness, in particular between higher weak 2-randomness and Π11-randomness. To do so we investigate classes of functions computable from Kleene’s O based on strong forms of the higher limit lemma.
    • Correction
    • Source
    • Cite
    • Save
    • Machine Reading By IdeaReader
    24
    References
    12
    Citations
    NaN
    KQI
    []