Coherence of reducibilities with randomness notions

DOI10.1007/S00224-017-9752-2zbMATH Open1436.03228OpenAlexW2594327249MaRDI QIDQ1787952FDOQ1787952

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

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

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)

Cites Work

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

Cited In (6)

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

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)