Coherence of reducibilities with randomness notions

DOI10.1007/S00224-017-9752-2zbMath1436.03228OpenAlexW2594327249MaRDI QIDQ1787952

Kenshi Miyabe

Publication date: 5 October 2018

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

Full work available at URL: https://doi.org/10.1007/s00224-017-9752-2

zbMATH Keywords

Schnorr reducibilityvan Lambalgen reducibilitydecidable machine

Mathematics Subject Classification ID

Other degrees and reducibilities in computability and recursion theory (03D30) Algorithmic randomness and dimension (03D32)

Cites Work

• Unnamed Item
• Reducibilities relating to Schnorr randomness
• Effectively approximating measurable sets by open sets
• Solovay functions and their applications in algorithmic randomness
• Prefix and plain Kolmogorov complexity characterizations of 2-randomness: simple proofs
• The \(K\)-degrees, low for \(K\) degrees, and weakly low for \(K\) sets
• On Kurtz randomness
• Limit complexities revisited
• Schnorr triviality and its equivalent notions
• Algorithmic randomness and measures of complexity
• Algorithmic Randomness and Complexity
• On initial segment complexity and degrees of randomness
• Schnorr trivial sets and truth-table reducibility
• Von Mises' definition of random sequences reconsidered
• Schnorr triviality and genericity
• Schnorr randomness
• Every 2-random real is Kolmogorov random
• Kolmogorov Complexity and Solovay Functions
• Reconciling Data Compression and Kolmogorov Complexity
• Randomness, relativization and Turing degrees

This page was built for publication: Coherence of reducibilities with randomness notions