Mathematical Logic Quarterly 57 (3):323-338 (2011)

Abstract
Schnorr randomness and computable randomness are natural concepts of random sequences. However van Lambalgen’s Theorem fails for both randomnesses. In this paper we define truth-table Schnorr randomness and truth-table reducible randomness, for which we prove that van Lambalgen's Theorem holds. We also show that the classes of truth-table Schnorr random reals relative to a high set contain reals Turing equivalent to the high set. It follows that each high Schnorr random real is half of a real for which van Lambalgen's Theorem fails. Moreover we establish the coincidence between triviality and lowness notions for truth-table Schnorr randomness. © 2011 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim
Keywords 03D25  03D15  Schnorr randomness  truth‐table reducibility  MSC (2010) 68Q30  van Lambalgen's Theorem  computably randomness
Categories (categorize this paper)
DOI 10.1002/malq.200910128
Options
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 69,066
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

Schnorr Randomness.Rodney G. Downey & Evan J. Griffiths - 2004 - Journal of Symbolic Logic 69 (2):533 - 554.
On Relative Randomness.Antonín Kučera - 1993 - Annals of Pure and Applied Logic 63 (1):61-67.

View all 8 references / Add more references

Citations of this work BETA

Van Lambalgen's Theorem and High Degrees.Johanna N. Y. Franklin & Frank Stephan - 2011 - Notre Dame Journal of Formal Logic 52 (2):173-185.
Nullifying Randomness and Genericity Using Symmetric Difference.Rutger Kuyper & Joseph S. Miller - 2017 - Annals of Pure and Applied Logic 168 (9):1692-1699.
Computable Randomness and Betting for Computable Probability Spaces.Jason Rute - 2016 - Mathematical Logic Quarterly 62 (4-5):335-366.

Add more citations

Similar books and articles

Subclasses of the Weakly Random Reals.Johanna N. Y. Franklin - 2010 - Notre Dame Journal of Formal Logic 51 (4):417-426.
Van Lambalgen's Theorem and High Degrees.Johanna N. Y. Franklin & Frank Stephan - 2011 - Notre Dame Journal of Formal Logic 52 (2):173-185.
Probabilistic Algorithmic Randomness.Sam Buss & Mia Minnes - 2013 - Journal of Symbolic Logic 78 (2):579-601.
Schnorr Randomness.Rodney G. Downey & Evan J. Griffiths - 2004 - Journal of Symbolic Logic 69 (2):533 - 554.
Hyperimmune-Free Degrees and Schnorr Triviality.Johanna N. Y. Franklin - 2008 - Journal of Symbolic Logic 73 (3):999-1008.
A C.E. Real That Cannot Be SW-Computed by Any Ω Number.George Barmpalias & Andrew E. M. Lewis - 2006 - Notre Dame Journal of Formal Logic 47 (2):197-209.
Schnorr Trivial Reals: A Construction. [REVIEW]Johanna N. Y. Franklin - 2008 - Archive for Mathematical Logic 46 (7-8):665-678.
Lowness for Kurtz Randomness.Noam Greenberg & Joseph S. Miller - 2009 - Journal of Symbolic Logic 74 (2):665-678.
Lowness and $\pi _{2}^{0}$ Nullsets.Rod Downey, Andre Nies, Rebecca Weber & Liang Yu - 2006 - Journal of Symbolic Logic 71 (3):1044 - 1052.
Independence, Randomness and the Axiom of Choice.Michiel van Lambalgen - 1992 - Journal of Symbolic Logic 57 (4):1274-1304.

Analytics

Added to PP index
2013-12-01

Total views
48 ( #233,933 of 2,498,786 )

Recent downloads (6 months)
1 ( #421,542 of 2,498,786 )

How can I increase my downloads?

Downloads

My notes