Lowness for the Class of Schnorr Random Reals

DOI10.1137/S0097539704446323MaRDI QIDQ5470706zbMATH OpenOpenAlexFDO

Authors Bjørn Kjos-Hanssen, André Nies, Frank Stephan

Publication date 1 June 2006

Published in SIAM Journal on Computing (Search for Journal in Brave)

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

zbMATH Keywords

computability theorylownessrandomnessrecursion theorySchnorr randomnessTuring degrees

Mathematics Subject Classification ID

Recursively (computably) enumerable sets and degrees (03D25) Other Turing degree structures (03D28) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Abstract: We answer a question of Ambos-Spies and Kuv{c}era in the affirmative. They asked whether, when a real is low for Schnorr randomness, it is already low for Schnorr tests.

Cited in

(28)

• Schnorr randomness for noncomputable measures
• On Kurtz randomness
• Highness properties close to PA completeness
• Unified characterizations of lowness properties via Kolmogorov complexity
• Schnorr triviality and its equivalent notions
• Lowness for difference tests
• Strong jump-traceability. I: The computably enumerable case
• Lowness properties and randomness
• Reducibilities relating to Schnorr randomness
• Characterizing lowness for Demuth randomness
• Defining a randomness notion via another
• Truth-table Schnorr randomness and truth-table reducible randomness
• Covering the Recursive Sets
• Lowness for Demuth Randomness
• Hyperimmune-free degrees and Schnorr triviality
• 𝐾-trivial degrees and the jump-traceability hierarchy
• Lowness for Kurtz randomness
• Strong jump-traceability. II: K-triviality
• Natural factors of the Muchnik lattice capturing IPC
• A \(K\)-trivial set which is not jump traceable at certain orders
• Strong jump-traceability
• Schnorr Trivial Reals: A construction
• Covering the recursive sets
• Low for random reals and positive-measure domination
• Lowness for integer-valued randomness
• Randomness and lowness notions via open covers
• Schnorr trivial reals: a construction
• Lowness of higher randomness notions

This page was built for publication: Lowness for the Class of Schnorr Random Reals

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