Reducibilities relating to Schnorr randomness

DOI10.1007/s00224-014-9583-3zbMath1408.68084OpenAlexW2081950252MaRDI QIDQ285517

Kenshi Miyabe

Publication date: 19 May 2016

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-014-9583-3

zbMATH Keywords

algorithmic randomnessintegral testSchnorr randomnessSchnorr reducibilityvan Lambalgen reducibility

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Related Items (2)

Coherence of reducibilities with randomness notions ⋮ A computable analysis of majorizing martingales

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Randomness and lowness notions via open covers
• The \(K\)-degrees, low for \(K\) degrees, and weakly low for \(K\) sets
• Incompleteness theorems for random reals
• Unified characterizations of lowness properties via Kolmogorov complexity
• Schnorr triviality and its equivalent notions
• Lowness properties and randomness
• Kolmogorov-Loveland randomness and stochasticity
• Computational randomness and lowness
• Randomness, Computability, and Density
• L1-Computability, Layerwise Computability and Solovay Reducibility
• Lowness notions, measure and domination
• Truth-table Schnorr randomness and truth-table reducible randomness
• Algorithmic Randomness and Complexity
• Traceable Sets
• When van Lambalgen’s Theorem fails
• On initial segment complexity and degrees of randomness
• Schnorr trivial sets and truth-table reducibility
• Schnorr randomness
• Computability and Randomness
• Reconciling Data Compression and Kolmogorov Complexity
• Lowness for the Class of Schnorr Random Reals
• Randomness, relativization and Turing degrees
• Van Lambalgen's theorem for uniformly relative Schnorr and computable randomness

This page was built for publication: Reducibilities relating to Schnorr randomness