Continuous higher randomness

DOI10.1142/S0219061317500040zbMATH Open1420.03100arXiv1503.04884OpenAlexW2531462202MaRDI QIDQ5268401FDOQ5268401

Laurent Bienvenu, Noam Greenberg, Benoit Monin

Publication date: 20 June 2017

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

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.

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

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

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)

Cites Work

• Algorithmic Randomness and Complexity
• Computability and randomness
• Set Theory
• The definition of random sequences
• Computable structures and the hyperarithmetical hierarchy
• Lowness properties and randomness
• Coherent randomness tests and computing the \(K\)-trivial sets
• On initial segment complexity and degrees of randomness
• Difference randomness
• Von Mises' definition of random sequences reconsidered
• Set theory.
• Title not available (Why is that?)
• Randomness via effective descriptive set theory
• Title not available (Why is that?)
• A Weakly 2-Random Set That Is Not Generalized Low
• Forcing with tagged trees
• Using random sets as oracles
• Lowness of higher randomness notions
• Randomness and differentiability
• Relative to any non-hyperarithmetic set
• Lowness for genericity
• Some measure theoretic results in effective descriptive set theory
• Bad oracles in higher computability and randomness
• Randomness in the higher setting
• Density, forcing, and the covering problem
• A New Proof of Friedman's Conjecture
• Higher randomness and forcing with closed sets
• Counting the changes of random Δ20 sets
• HIGHER RANDOMNESS AND GENERICITY

Cited In (11)

• GENERICITY AND RANDOMNESS WITH ITTMS
• Measure-theoretic applications of higher Demuth's theorem
• Title not available (Why is that?)
• Parallel and Serial Jumps of Weak Weak König’s Lemma
• A COMPARISON OF VARIOUS ANALYTIC CHOICE PRINCIPLES
• Effectively closed subgroups of the infinite symmetric group
• RANDOMNESS VIA INFINITE COMPUTATION AND EFFECTIVE DESCRIPTIVE SET THEORY
• SEARCHING FOR AN ANALOGUE OF ATR₀ IN THE WEIHRAUCH LATTICE
• Lowness of higher randomness notions
• Bad oracles in higher computability and randomness
• HIGHER RANDOMNESS AND GENERICITY

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)