Continuous higher randomness

DOI10.1142/S0219061317500040MaRDI QIDQ5268401zbMATH OpenOpenAlexFDO

Authors Laurent Bienvenu, Noam Greenberg, Benoit Monin

Publication date 20 June 2017

Published in Journal of Mathematical Logic (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1503.04884

zbMATH Keywords

higher randomness\(K\)-trivialitycollapsing approximationcontinuous relativized

Mathematics Subject Classification ID

Algorithmic randomness and dimension (03D32) Computability and recursion theory on ordinals, admissible sets, etc. (03D60)

Abstract: We investigate the role of continuous reductions and continuous relativisation 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 characterisations of lowness for Martin-L"of randomness. We also characterise 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 $P{i}_1^1$-randomness. To do so we investigate classes of functions computable from Kleene's~$O$ based on strong forms of the higher limit lemma.

Recommendations

• Higher randomness and genericity
• Randomness in the higher setting
• Lowness of higher randomness notions
• Bad oracles in higher computability and randomness
• Randomness, relativization and Turing degrees

Cites work

• scientific article; zbMATH DE number 4008384 (Why is no real title available?)
• scientific article; zbMATH DE number 194101 (Why is no real title available?)
• A Weakly 2-Random Set That Is Not Generalized Low
• A new proof of Friedman's conjecture
• Algorithmic randomness and complexity.
• Bad oracles in higher computability and randomness
• Coherent randomness tests and computing the \(K\)-trivial sets
• Computability and randomness
• Computable structures and the hyperarithmetical hierarchy
• Counting the changes of random \(\Delta_2^0\) sets
• Density, forcing, and the covering problem
• Difference randomness
• Forcing with tagged trees
• Higher randomness and forcing with closed sets
• Higher randomness and genericity
• Lowness for genericity
• Lowness of higher randomness notions
• Lowness properties and randomness
• On initial segment complexity and degrees of randomness
• Randomness and differentiability
• Randomness in the higher setting
• Randomness via effective descriptive set theory
• Relative to any non-hyperarithmetic set
• Set Theory
• Set theory.
• Some measure theoretic results in effective descriptive set theory
• The definition of random sequences
• Using random sets as oracles
• Von Mises' definition of random sequences reconsidered

Cited in

(13)

• Searching for an analogue of \(\text{ATR}_0\) in the Weihrauch lattice
• Measure-theoretic applications of higher Demuth's theorem
• scientific article; zbMATH DE number 7204368 (Why is no real title available?)
• Parallel and Serial Jumps of Weak Weak König’s Lemma
• Higher randomness and genericity
• Higher randomness and lim-sup forcing within and beyond hyperarithmetic
• Genericity and randomness with ITTMs
• A COMPARISON OF VARIOUS ANALYTIC CHOICE PRINCIPLES
• Randomness in the higher setting
• Effectively closed subgroups of the infinite symmetric group
• RANDOMNESS VIA INFINITE COMPUTATION AND EFFECTIVE DESCRIPTIVE SET THEORY
• Lowness of higher randomness notions
• Bad oracles in higher computability and randomness

This page was built for publication: Continuous higher randomness

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5268401)