Coherence of reducibilities with randomness notions

DOI10.1007/S00224-017-9752-2MaRDI QIDQ1787952zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• scientific article; zbMATH DE number 1834658
• Randomness and reducibility
• Coarse reducibility and algorithmic randomness
• Reducibilities relating to Schnorr randomness
• Randomness notions and partial relativization

Cites work

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

Cited in

(6)

• Randomness notions and reverse mathematics
• Coarse reducibility and algorithmic randomness
• Defining a randomness notion via another
• Randomness notions and partial relativization
• A note on the decidability of de Finetti's coherence
• Random reduction consistency of the Weber set, the core and the anti-core

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

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