Schnorr triviality and its equivalent notions

DOI10.1007/s00224-013-9506-8zbMath1336.03048OpenAlexW2068668183MaRDI QIDQ2354579

Kenshi Miyabe

Publication date: 20 July 2015

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

Full work available at URL: https://doi.org/10.1007/s00224-013-9506-8

zbMATH Keywords

algorithmic randomnessSchnorr randomnessuniform relativizationlowness for uniform Schnorr randomnessSchnorr triviality

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Algorithmic randomness and dimension (03D32)

Related Items (3)

Reducibilities relating to Schnorr randomness ⋮ Coherence of reducibilities with randomness notions ⋮ Unified characterizations of lowness properties via Kolmogorov complexity

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Randomness and lowness notions via open covers
• Zufälligkeit und Wahrscheinlichkeit. Eine algorithmische Begründung der Wahrscheinlichkeitstheorie. (Randomness and probability. An algorithmic foundation of probability theory)
• Lowness properties and randomness
• Computational randomness and lowness
• Lowness notions, measure and domination
• Uniform Kurtz randomness
• Truth-table Schnorr randomness and truth-table reducible randomness
• On Schnorr and computable randomness, martingales, and machines
• Algorithmic Randomness and Complexity
• Traceable Sets
• Schnorr trivial sets and truth-table reducibility
• Relativizations of randomness and genericity notions
• Using random sets as oracles
• Schnorr randomness
• Reconciling Data Compression and Kolmogorov Complexity
• Lowness for the Class of Schnorr Random Reals
• The definition of random sequences
• A van Lambalgen theorem for Demuth randomness
• Van Lambalgen's theorem for uniformly relative Schnorr and computable randomness

This page was built for publication: Schnorr triviality and its equivalent notions