Truth-table Schnorr randomness and truth-table reducible randomness

DOI10.1002/malq.200910128zbMath1220.03043OpenAlexW2074699400MaRDI QIDQ3008061

Kenshi Miyabe

Publication date: 17 June 2011

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

Full work available at URL: https://doi.org/10.1002/malq.200910128

zbMATH Keywords

lownessSchnorr randomnesstrivialitytruth-table reducibilityvan Lambalgen's theoremcomputably randomness

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Complexity of computation (including implicit computational complexity) (03D15) Recursively (computably) enumerable sets and degrees (03D25) Algorithmic randomness and dimension (03D32)

Related Items (10)

Nullifying randomness and genericity using symmetric difference ⋮ Reducibilities relating to Schnorr randomness ⋮ When does randomness come from randomness? ⋮ Sub-computable Bounded Pseudorandomness ⋮ CHARACTERIZING LOWNESS FOR DEMUTH RANDOMNESS ⋮ Schnorr randomness for noncomputable measures ⋮ Computable randomness and betting for computable probability spaces ⋮ Unified characterizations of lowness properties via Kolmogorov complexity ⋮ Schnorr triviality and its equivalent notions ⋮ A Church-Turing thesis for randomness?

Cites Work

• Unnamed Item
• On relative randomness
• Classical recursion theory. The theory of functions and sets of natural numbers
• Information-theoretic characterizations of recursive infinite strings
• Classical recursion theory. Vol. II
• Some results on effective randomness
• Lowness properties and randomness
• Kolmogorov-Loveland randomness and stochasticity
• On Schnorr and computable randomness, martingales, and machines
• Algorithmic Randomness and Complexity
• When van Lambalgen’s Theorem fails
• Schnorr trivial sets and truth-table reducibility
• Lowness for the class of random sets
• Relativizations of randomness and genericity notions
• Using random sets as oracles
• Schnorr randomness
• Computability and Randomness
• Lowness for the Class of Schnorr Random Reals
• A unified approach to the definition of random sequences

This page was built for publication: Truth-table Schnorr randomness and truth-table reducible randomness